小Z的袜子
wangyuchen
2018-07-08 10:14:21
## 题目 ##
[传送门](https://www.lydsy.com/JudgeOnline/problem.php?id=2038)
## 做法 & 思路 ##
这题其实是求
$$ \sum_i {cnt[i] \choose 2} \over {r-l+1 \choose 2} $$
$cnt[i]$是颜色i在$[l, r]$中的出现次数
我们知道${a \choose 2} = a \times (a-1) = a^2 - a$
于是， 分子就变成了
$$ {\sum_i{cnt[i]^2} -\sum_i{cnt[i]}} \over {2} $$
分母就变成了
$$ {(r-l+1)^2 - (r-l+1)} \over {2} $$
于是， 一次查询的答案就是
$$ {\sum_i{cnt[i]^2} -\sum_i{cnt[i]}} \over {(r-l+1)^2 - (r-l+1)} $$
我们可以使用莫队算法
其中分子中的$\sum_i{cnt[i]}$是不需要维护的， 因为很明显他就等于$r-l+1$
然后我们只需要维护$\sum_i{cnt[i]^2}$
这题就做完了
## 代码 ##
```cpp
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 50010;
int belong[N], block;
int color[N];
struct Query
{ int l, r, id;
Query() { }
Query(int _1, int _2, int _3) : l(_1), r(_2), id(_3) { }
} a[N];
bool cmp(Query x, Query y) { return belong[x.l] == belong[y.l] ? x.r < y.r : belong[x.l] < belong[y.l]; }
LL sqr(LL x) { return x * x; }
LL cnt[N];
LL sum;
LL Ans1[N], Ans2[N];
void update(int x, int opt)
{ sum -= sqr(cnt[color[x]]);
cnt[color[x]] += opt;
sum += sqr(cnt[color[x]]);
}
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); }
int main()
{ int n, m;
scanf("%d %d", &n, &m);
block = (int) sqrt(n + 0.5);
for (int i = 1; i <= n; i++)
belong[i] = (i-1) / block + 1;
for (int i = 1; i <= n; i++)
scanf("%d", &color[i]);
for (int i = 1; i <= m; i++)
scanf("%d %d", &a[i].l, &a[i].r),
a[i].id = i;
sort(a+1, a+1+m, cmp);
int l = 1, r = 0;
for (int i = 1; i <= m; i++)
{ for (; r < a[i].r; r++)
update(r+1, 1);
for (; r > a[i].r; r--)
update(r, -1);
for (; l < a[i].l; l++)
update(l, -1);
for (; l > a[i].l; l--)
update(l-1, 1);
if (a[i].l == a[i].r)
{ Ans1[a[i].id] = 0;
Ans2[a[i].id] = 1;
continue;
}
Ans1[a[i].id] = sum - (a[i].r - a[i].l + 1);
Ans2[a[i].id] = sqr((LL) (a[i].r - a[i].l + 1)) - (LL) (a[i].r - a[i].l + 1);
LL d = gcd(Ans1[a[i].id], Ans2[a[i].id]);
Ans1[a[i].id] /= d;
Ans2[a[i].id] /= d;
}
for (int i = 1; i <= m; i++)
printf("%lld/%lld\n", Ans1[i], Ans2[i]);
return 0;
}
```