(color{#0066ff}{ 题目描述 })
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
然而数据中有L=R的情况，请特判这种情况，输出0/1。
(color{#0066ff}{输入格式})、
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。
(color{#0066ff}{输出格式})
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）
(color{#0066ff}{输入样例})
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
(color{#0066ff}{输出样例})
2/5
0/1
1/1
4/15
(color{#0066ff}{数据范围与提示})
30%的数据中 N,M ≤ 5000；
60%的数据中 N,M ≤ 25000；
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。
(color{#0066ff}{ 题解 })
莫队第一题。。。
莫队的使用有一些限制
首先，问题必须离线
然后，要支持分块
其次，对于区间的转移要很快，一般为(O(1))
这题，显然一个区间的答案为(frac{sum C_{t_i}^2}{C_{len}^2})
其中len为区间长度，(t_i)为颜色为i的袜子在区间中的个数
化简之后变为了(frac{sum t_i*(t_i-1)}{len *(len-1)})
发现分母是固定的，这题又要单独输出分子分母，于是只看分子就行了
显然来了一个数或删掉一个数，我们都可以把当前贡献减掉再加上新的贡献
于是第二个条件满足了， 第一个显然满足，第二个，由于是区间查询，也满足了
那么怎么排序才能保证复杂度呢
我们对于左端点在一个块的，按块的奇偶对r排序，那么r是一个波浪形
如果左端点不在一个块，则按块的编号排序
那么实际上l的移动都是在一个块内，移动完再去下一个块
r的移动是一个波浪，在一个块内单调
那么总复杂度显然是(O(nsqrt n))
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
using std::pair;
using std::make_pair;
const int maxn = 5e4 + 10;
int bel[maxn], n, m, a[maxn];
LL t[maxn];
struct node {
LL l, r, id;
friend bool operator < (const node &a, const node &b) {
if(bel[a.l] == bel[b.l]) return bel[a.l] & 1? a.r < b.r : a.r > b.r;
return bel[a.l] < bel[b.l];
}
LL tot() { return (r - l + 1) * (r - l); }
}e[maxn];
pair<LL, LL> ans[maxn];
LL tot;
LL l = 1, r;
void add(int i) {
t[i]++;
if(t[i] >= 2) tot = tot + t[i] * (t[i] - 1) - (t[i] - 1) * (t[i] - 2);
}
void del(int i) {
t[i]--;
if(t[i] >= 1) tot = tot + t[i] * (t[i] - 1) - t[i] * (t[i] + 1);
}
LL gcd(LL x, LL y) { return y? gcd(y, x % y) : x; }
void out(const pair<LL, LL> &a) {
LL x = a.first, y = a.second;
LL gc = gcd(x, y);
x /= gc, y /= gc;
printf("%lld/%lld
", x, y);
}
int main() {
n = in(), m = in();
int len = sqrt(n);
for(int i = 1; i <= n; i++) a[i] = in(), bel[i] = (i - 1) / len + 1;
for(int i = 1; i <= m; i++) e[i].l = in(), e[i].r = in(), e[i].id = i;
std::sort(e + 1, e + m + 1);
for(int i = 1; i <= m; i++) {
while(l > e[i].l) add(a[--l]);
while(l < e[i].l) del(a[l++]);
while(r < e[i].r) add(a[++r]);
while(r > e[i].r) del(a[r--]);
if(e[i].l == e[i].r) ans[e[i].id] = make_pair(0, 1);
else ans[e[i].id] = make_pair(tot, e[i].tot());
}
for(int i = 1; i <= m; i++) out(ans[i]);
return 0;
}