Description
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
Input
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。
Output
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）
Sample Input
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
Sample Output
2/5
0/1
1/1
4/15
【样例解释】
询问1：共C(5,2)=10种可能，其中抽出两个2有1种可能，抽出两个3有3种可能，概率为(1+3)/10=4/10=2/5。
询问2：共C(3,2)=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/1。
询问3：共C(3,2)=3种可能，均为抽出两个3，概率为3/3=1/1。
注：上述C(a, b)表示组合数，组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。
【数据规模和约定】
30%的数据中 N,M ≤ 5000；
60%的数据中 N,M ≤ 25000；
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。
Solution
可以离线求解的区间问题，并且满足莫队的条件——莫队
看一个区间的答案
\(\displaystyle ans=\sum_{color=1}\frac{C_{cnt_{color}}^2}{C_{len}^2}\)
\(\displaystyle ~~~~~~~=\frac{2\sum_{color=1}C_{cnt_{color}}^2}{len(len-1)}\)
\(\displaystyle ~~~~~~~=\frac{\sum_{color=1}cnt_{color}(cnt_{color}-1)}{len(len-1)}\)
莫队维护分数上面的东西
对于区间平移的时候，把要修改的数字原来的贡献减去，数字修改完后，加上新的数字的贡献
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=50000+10;
int n,m,q,unit,A[MAXN],Be[MAXN],cnt[MAXN];
ll sum,fst[MAXN],scd[MAXN];
struct node{
int l,r,id;
inline bool operator < (const node &A) const {
return Be[l]==Be[A.l]?r<A.r:l<A.l;
};
};
node query[MAXN];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void modify(int x,int k)
{
sum-=1ll*cnt[x]*(cnt[x]-1);
cnt[x]+=k;
sum+=1ll*cnt[x]*(cnt[x]-1);
}
inline ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
read(n);read(q);
unit=std::sqrt(n);
for(register int i=1;i<=n;++i)read(A[i]),Be[i]=i/unit+1;
for(register int i=1;i<=q;++i)
{
read(query[i].l),read(query[i].r);
query[i].id=i;
}
std::sort(query+1,query+q+1);
int l=1,r=0;
for(register int i=1;i<=q;++i)
{
while(l<query[i].l)modify(A[l++],-1);
while(l>query[i].l)modify(A[--l],1);
while(r<query[i].r)modify(A[++r],1);
while(r>query[i].r)modify(A[r--],-1);
if(query[i].l==query[i].r)fst[query[i].id]=0,scd[query[i].id]=1;
else fst[query[i].id]=sum,scd[query[i].id]=1ll*(r-l+1)*(r-l);
}
for(register int i=1;i<=q;++i)
{
ll d=gcd(scd[i],fst[i]);
fst[i]/=d,scd[i]/=d;
write(fst[i],'/');write(scd[i],'\n');
}
return 0;
}