BZOJ 2038: [2009国家集训队]小Z的袜子(hose)（莫队算法）

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 #define N 50010
 7 typedef long long LL;
 8 struct node {
 9     int l, r, id;
10     LL fz, fm;
11 } p[N];
12 int n, m, kuai;
13 LL a[N], col[N], ans;
14 
15 void update(int id, int w) { ans -= col[a[id]]; col[a[id]] += w; ans += col[a[id]]; }
16 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
17 bool cmp(const node &a, const node &b) {
18     if(a.l / kuai == b.l / kuai) return a.r < b.r;
19     return a.l / kuai < b.l / kuai;
20 }
21 
22 int main() {
23    while(~scanf("%d%d", &n, &m)) {
24         memset(col, 0, sizeof(col));
25         for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
26         for(int i = 1; i <= m; i++) scanf("%d%d", &p[i].l, &p[i].r), p[i].id = i;
27         int L = 1, R = 0; kuai = sqrt(n);
28         sort(p + 1, p + 1 + m, cmp);
29         LL fz = 0, fm = 0; ans = 0;
30         for(int i = 1; i <= m; i++) {
31             int l = p[i].l, r = p[i].r;
32             for( ; R < r; R++) update(R + 1, 1);
33             for( ; R > r; R--) update(R, -1);
34             for( ; L > l; L--) update(L - 1, 1);
35             for( ; L < l; L++) update(L, -1);
36             if(l == r) { p[i].fz = 0; p[i].fm = 1; continue; }
37             fz = ans - (p[i].r - p[i].l + 1); fm = (r - l + 1) * (r - l);
38             LL yue = gcd(fz, fm); fz /= yue; fm /= yue;
39             p[i].fz = fz; p[i].fm = fm;
40         }
41         sort(p + 1, p + 1 + m, cmpid);
42         for(int i = 1; i <= m; i++) printf("%lld/%lld\n", p[i].fz, p[i].fm);
43     }
44     return 0;
45 }