题面
题解
考虑莫队算法，首先对询问进行分块（分块大小为$sqrt(n)$），对于同一个块内的询问，按照左端点为第一关键字，右端点为第二关键字排序。我们统计这个区间内相同的颜色有多少个，假设某种颜色$i$有$j$个，则贡献就是$j\times(j-1)$，最后记得化成既约分数。
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;
using std::set;
template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}
const int N = 5e4 + 10, M = 5e4 + 10;
int n, m, c[N], siz, blo, t, l, r, v[N];
struct Ques { int x, y, z; } q[M], b[M];
inline bool cmp1 (Ques a, Ques b) { return a.x < b.x; }
inline bool cmp2 (Ques a, Ques b) { return a.y < b.y; }
ll up[M], down[M], _gcd, tmp;
template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
void modify (int st, int ed, int flag) {
for(int i = st; i < ed; ++i) {
tmp -= 1ll * v[c[i]] * (v[c[i]] - 1);
v[c[i]] += flag;
tmp += 1ll * v[c[i]] * (v[c[i]] - 1);
}
}
int main () {
#ifdef OFFLINE_JUDGE
freopen("233.in", "r", stdin);
freopen("233.out", "w", stdout);
#endif
read(n), read(m);
for(int i = 1; i <= n; ++i) read(c[i]);
for(int i = 1; i <= m; ++i)
read(q[i].x), read(q[i].y), q[i].z = i;
sort(&q[1], &q[m + 1], cmp1);
siz = sqrt(n), blo = (n / siz) + (n % siz != 0);
for(int i = 0, j = 1; i < blo; ++i) {
t = 0;
while(j <= m && q[j].x > i * siz && q[j].x <= (i + 1) * siz) b[++t] = q[j++];
sort(&b[1], &b[t + 1], cmp2);
l = b[1].x, r = b[1].x - 1, tmp = 0;
memset(v, 0, sizeof v);
for(int k = 1; k <= t; ++k) {
if(b[k].x == b[k].y) {
up[b[k].z] = 0, down[b[k].z] = 1;
continue;
}
if(l < b[k].x) modify(l, b[k].x, -1);
else if(l > b[k].x) modify(b[k].x, l, 1);
if(r < b[k].y) modify(r + 1, b[k].y + 1, 1);
else if(r > b[k].y) modify(b[k].y + 1, r + 1, -1);
up[b[k].z] = tmp, down[b[k].z] = b[k].y - b[k].x + 1;
l = b[k].x, r = b[k].y;
}
}
for(int i = 1; i <= m; ++i) {
if(!down[i] || !up[i]) { puts("0/1"); continue; }
down[i] = down[i] * (down[i] - 1);
tmp = gcd(up[i], down[i]);
printf("%lld/%lld\n", up[i] / tmp, down[i] / tmp);
}
return 0;
}