BZOJ 2038 莫队算法

链接：

http://www.lydsy.com/JudgeOnline/problem.php?id=2038

题意：

中文题目就不说题意了

题解：

这道题好像是莫队出的。。在bzoj上re了19发之后跑到源题目地址上提交，妥妥的ac

wqnmlgb bzoj

这个oj居然还评测代码风格，93分哈哈哈

代码：

31 struct node {
32     ll l, r, id;
33 }q[MAXN];
34 
35 ll n, m;
36 ll a[MAXN];
37 ll pos[MAXN];
38 pair<ll, ll> ans[MAXN];
39 ll sum[MAXN];
40 
41 bool cmp(node a, node b) {
42     if (pos[a.l] == pos[b.l]) return a.r < b.r;
43     return a.l < b.l;
44 }
45 
46 ll L = 1, R = 0;
47 ll Sum = 0;
48 
49 void update(ll x, ll add) {
50     Sum -= sum[a[x]] * (sum[a[x]] - 1) / 2;
51     sum[a[x]] += add;
52     Sum += sum[a[x]] * (sum[a[x]] - 1) / 2;
53 }
54 
55 ll gcd(ll a, ll b) {
56     return b == 0 ? a : gcd(b, a%b);
57 }
58 
59 int main() {
60     ios::sync_with_stdio(false), cin.tie(0);
61     cin >> n >> m;
62     ll sz = sqrt(n);
63     rep(i, 1, n + 1) {
64         cin >> a[i];
65         pos[i] = i / sz;
66     }
67     rep(i, 0, m) {
68         cin >> q[i].l >> q[i].r;
69         q[i].id = i;
70     }
71     sort(q, q + m, cmp);
72     rep(i, 0, m) {
73         while (L < q[i].l) update(L++, -1);
74         while (L > q[i].l) update(--L, 1);
75         while (R < q[i].r) update(++R, 1);
76         while (R > q[i].r) update(R--, -1);
77         ll a = Sum, b = (q[i].r - q[i].l + 1)*(q[i].r - q[i].l) / 2;
78         ll t = gcd(a, b);
79         if (a == 0 || b == 0 || t == 0) {
80             ans[q[i].id] = mp(0, 1);
81             continue;
82         }
83         ans[q[i].id].first = a / t;
84         ans[q[i].id].second = b / t;
85     }
86     rep(i, 0, m) cout << ans[i].first << '/' << ans[i].second << endl;
87     return 0;
88 }