洛谷 - P1494 [国家集训队]小Z的袜子

传送门：洛谷 - P1494

题目描述

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

具体来说，小Z把这 $N$ 只袜子从 1 到 $N$ 编号，然后从编号 $L$ 到 $R$

你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个$(L,R)$以方便自己选择。

输入描述

输入文件第一行包含两个正整数 $N$ 和 $M$。$N$为袜子的数量，$M$为小Z所提的询问的数量。接下来一行包含 $N$ 个正整数 $C_i$
​$C_i$表示第 $i$ 只袜子的颜色，相同的颜色用相同的数字表示。再接下来 $M$ 行，每行两个正整数 $L$, $R$表示一个询问。

输出描述

包含 $M$ 行，对于每个询问在一行中输出分数 $A/B$ 表示从该询问的区间 $[L,R]$ 中随机抽出两只袜子颜色相同的概率。若该概率为 0 则输出 0/1，否则输出的$A/B$必须为最简分数。

思路分析

对于每种颜色的袜子，抽到两只的概率为 $\frac{cnt * (cnt-1)}{(R-L+1) * (R-L) }$

所以总概率就是 $\frac{\sum_{i=1}^x cnt * (cnt-1) }{(R-L+1) * (R-L) }$

样例输入

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

样例输出

2/5
0/1
1/1
4/15

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;

struct node {
    int l, r, k;
} q[N];

int bel[N];
ll a[N], cnt[N], res;
pair<ll, ll>ans[N];

bool cmp(node a, node b) {
    return bel[a.l] == bel[b.l] ? a.r < b.r : bel[a.l] < bel[b.l];
}

void add(int x) {
    if (cnt[a[x]] > 0)
        res -= cnt[a[x]] * (cnt[a[x]] - 1);
    cnt[a[x]]++;
    res += cnt[a[x]] * (cnt[a[x]] - 1);
}

void del(int x) {
    if (cnt[a[x]] > 0)
        res -= cnt[a[x]] * (cnt[a[x]] - 1);
    cnt[a[x]]--;
    if (cnt[a[x]] > 0)
        res += cnt[a[x]] * (cnt[a[x]] - 1);
}

ll gcd(ll x, ll y) {
    return !y ? x : gcd(y, x % y);
}

int main() {

#ifdef xiaofan
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif

    int n, m;
    cin >> n >> m;
    int size = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        bel[i] = i / size;
    }
    for (int i = 0; i < m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].k = i;
    }
    sort(q, q + m, cmp);
    ll l = 1, r = 0;
    for (int i = 0; i < m; i++) {
        while (q[i].l < l)add(--l);
        while (q[i].r > r)add(++r);
        while (q[i].l > l)del(l++);
        while (q[i].r < r)del(r--);
        if (!res) {
            ans[q[i].k].fi = 0;
            ans[q[i].k].se = 1;
            continue;
        }
        ll g = __gcd(res, (r - l + 1) * (r - l));
        ans[q[i].k].fi = res / g;
        ans[q[i].k].se = (r - l + 1) * (r - l) / g;
    }

    for (int i = 0; i < m; i++)
        printf("%lld/%lld\n", ans[i].fi, ans[i].se);





    return 0;
}