【BZOJ 2038】【2009 国家集训队】小Z的袜子(hose) 分块+莫队

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50003
#define read(x) x=getint()
#define sqr(x) (x)*(x)
using namespace std;
typedef long long LL;
inline int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = - 1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
}
struct node {
int id, l, r;
} q[N];
LL sum, fz[N], fm[N], s[N];
int n, a[N], block[N], bel[N], m;
inline bool cmp(node A, node B) {return bel[A.l] == bel[B.l] ? A.r < B.r : A.l < B.l;}
inline void change(int x, int del) {
sum -= sqr(s[x]);
s[x] += del;
sum += sqr(s[x]);
}
inline LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
int main() {
read(n); read(m);
for(int i = 1; i <= n; ++i)
read(a[i]);
for(int i = 1; i <= m; ++i)
read(q[i].l), read(q[i].r), q[i].id = i;int t = ceil(sqrt(n)), tmp = 0, cnt = 0;
for(int i = 1; i <= n; ++i) {
bel[i] = cnt;
++tmp;
if (tmp == t)
tmp = 0, ++cnt;
}sort(q + 1, q + m + 1, cmp);int l = q[1].l, r = q[1].r;
for(int i = l; i <= r; ++i) {
sum -= sqr(s[a[i]]);
++s[a[i]];
sum += sqr(s[a[i]]);
}
fz[q[1].id] = sum - (r - l + 1);
fm[q[1].id] = (r - l) * (r - l + 1);
for(int i = 2; i <= m; ++i) {
int tl = q[i].l, tr = q[i].r, tid = q[i].id;
LL tlen = tr - tl + 1;
while (l < tl) change(a[l++], -1);
while (l > tl) change(a[--l], 1);
while (r < tr) change(a[++r], 1);
while (r > tr) change(a[r--], -1);
fz[tid] = sum - tlen;
fm[tid] = tlen * (tlen - 1);
}
for(int i = 1; i <= m; ++i) {
if (fz[i] <= 0 || fm[i] <= 0)
puts("0/1");
else {
LL tong = gcd(fz[i], fm[i]);
printf("%lld/%lld\n", fz[i] / tong, fm[i] / tong);
}
}
return 0;
}