任意门：https://www.lydsy.com/JudgeOnline/problem.php?id=2038
题意概括：
有 N 只袜子（分别编号为1~N)，有 M 次查询 （L， R）里面随机拿两只袜子，拿到相同颜色袜子的概率是多少。
解题思路：
莫队算法经典题，暴力找出区间内相同颜色的袜子的个数，排列组合最后得出结果。
入门题，当模版。
AC code：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std; const int MAXN = 5e4+;
int pos[MAXN], c[MAXN];
LL s[MAXN], res;
int N, M, L = , R = ; LL gcd(LL a, LL b){return b==?a:gcd(b, a%b);}
LL sqr(LL x){return x*x;}
struct date{
int l, r, id;
LL so, mo;
}q[MAXN];
bool cmp(date a, date b){
if(pos[a.l]==pos[b.l]) return a.r < b.r;
return a.l < b.l;
}
bool CMP(date a, date b){
return a.id < b.id;
}
void Update(int x, int add)
{
//res-=sqr(s[c[x]]);
res-=s[c[x]]*s[c[x]];
s[c[x]]+=add;
res+=s[c[x]]*s[c[x]];
//res+=sqr(s[c[x]]);
} int main()
{
scanf("%d%d", &N, &M);
int sz = sqrt(N);
for(int i = ; i <= N; i++){
scanf("%d", &c[i]);
//pos[i] = (i-1)/sz+1;
pos[i] = i/sz;
}
for(int i = ; i <= M; i++){
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q+, q+M+, cmp);
for(int i = ; i <= M; i++){
while(R < q[i].r){R++; Update(R, );}
while(R > q[i].r){Update(R, -); R--;}
while(L < q[i].l){Update(L, -); L++;}
while(L > q[i].l){L--; Update(L, );}
if(q[i].l == q[i].r){
q[i].so = ;q[i].mo = ;
continue;
}
q[i].so = res-(q[i].r-q[i].l+);
q[i].mo = (LL)(q[i].r-q[i].l+)*(q[i].r-q[i].l);
LL k = gcd(q[i].so, q[i].mo);
q[i].so/=k;q[i].mo/=k;
}
sort(q+, q+M+, CMP);
for(int i = ; i <= M; i++){
printf("%lld/%lld\n", q[i].so, q[i].mo);
}
return ;
}