P1494 [国家集训队] 小 Z 的袜子
大意
给出一段区间的颜色，区间询问，求某段区间两个点颜色相同的概率(用分数表示)
思路
发现询问和查询隔离，考虑莫队。
然后我们的修改是不是只需要考虑多一个或者少一个点，那么这个很好办啊。
如果记当前答案(分子)是 \(\text{ans}\)，则在加入点的时候，\(\text{ans}\) 先加上原来这个新加入点颜色的贡献，如果是删点的花就先把删掉的这个点的贡献减去，\(\text{ans}\) 的贡献就减去减掉后的这个贡献。
然后注意 long long 即可。
代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;#define int long long
const int MAXN = 50005;
int B = 0;
struct node{int l, r, id;bool operator < (const node &t) const{if(l / B == t.l / B) return r < t.r;return l / B < t.l / B;}
} q[MAXN];
int cnt[MAXN], col[MAXN];
int n, m, ans1[MAXN], ans2[MAXN], A, BB;int gcd(int a, int b){return (b == 0) ? a : gcd(b, a % b);
}void add(int x){A += cnt[x];cnt[x] ++;
}void del(int x){cnt[x] --;A -= cnt[x];
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;B = sqrt(n);for(int i = 1;i <= n;i ++){cin >> col[i];}for(int i = 1;i <= m;i ++){cin >> q[i].l >> q[i].r;q[i].id = i;}sort(q + 1, q + m + 1);for(int l = 1, r = 0, i = 1;i <= m;i ++){if(q[i].l == q[i].r){ans1[q[i].id] = 0;ans2[q[i].id] = 1;continue;}while(l > q[i].l) add(col[-- l]);while(l < q[i].l) del(col[l ++]);while(r < q[i].r) add(col[++ r]);while(r > q[i].r) del(col[r --]);BB = (r - l + 1) * (r - l) / 2;int g = gcd(A, BB);ans1[q[i].id] = A / g;ans2[q[i].id] = BB / g;}for(int i = 1;i <= m;i ++){cout << ans1[i] << '/' << ans2[i] << '\n';}return 0;
}