原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ2038.html
给定一个数列。长度为 $n$ ，有 $m$ 次询问，每次询问在 区间 $[L,R]$ 中任选两个，问选到相同数的概率为多少，以最简分数形式输出。
$n,m\leq 50000$
莫队裸题 13分钟 1A
我怎么会来做这种傻逼题
#include <bits/stdc++.h>
using namespace std;
const int N=50005;
int n,m,a[N],tax[N];
struct Query{
int L,R,id,ans;
}q[N];
bool cmp(Query a,Query b){
int La=a.L>>8,Lb=b.L>>8;
if (La!=Lb)
return La<Lb;
return a.R<b.R;
}
bool cmpid(Query a,Query b){
return a.id<b.id;
}
int calc(int x){
return 1LL*x*(x-1)/2;
}
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=m;i++)
scanf("%d%d",&q[i].L,&q[i].R),q[i].id=i;
sort(q+1,q+m+1,cmp);
memset(tax,0,sizeof tax);
int L=1,R=0,ans=0;
for (int i=1;i<=m;i++){
int Lnow=q[i].L,Rnow=q[i].R;
while (R<q[i].R)
ans+=(tax[a[++R]]++);
while (L>q[i].L)
ans+=(tax[a[--L]]++);
while (R>q[i].R)
ans-=(--tax[a[R--]]);
while (L<q[i].L)
ans-=(--tax[a[L++]]);
q[i].ans=ans;
}
sort(q+1,q+m+1,cmpid);
for (int i=1;i<=m;i++){
int a=q[i].ans,b=calc(q[i].R-q[i].L+1),g=gcd(a,b);
printf("%d/%d\n",a/g,b/g);
}
return 0;
}
BZOJ2038 [2009国家集训队]小Z的袜子(hose) 莫队
原文：https://www.cnblogs.com/zhouzhendong/p/BZOJ2038.html