题目概述:

小Z把N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

---

图片为本人原创

然后考虑莫队

会发现当\(cnt[i]-1\)时，对答案的贡献为\(1-2*cnt[i]\)

当\(cnt[i]+1\)时，对答案的贡献为\(1+2*cnt[i]\)

然后这个题目就这样解决辣

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn=5e4+20;

ll n,m,len;

ll sock[maxn],b[maxn],cnt[maxn];

ll gcd(ll a,ll b)

{

	if(!b) return a;

	return gcd(b,a%b);

}

ll tot=0;

inline void add(ll x){tot+=((cnt[x]<<1)|1),++cnt[x];}

inline void del(ll x){tot+=1-(cnt[x]<<1),--cnt[x];}

struct cc{

	ll x,y;

}ans[maxn];

struct query{

	ll l,r,id;

}q[maxn];

inline bool cmp(query x,query y)

{

	if(b[x.l]<b[y.l]) return 1;

	if(b[x.l]>b[y.l]) return 0;

	if(b[x.l]&1) return x.r<y.r;//奇偶优化

	return y.r>x.r;

}

void div(ll a,ll b,ll id)

{

	ll qaq=gcd(a,b);

	a/=qaq,b/=qaq;

	ans[id].x=a,ans[id].y=b;

	return ;

}

int main()

{

	scanf("%lld%lld",&n,&m);

	len=n/sqrt((m<<1)/3);//毒瘤lxl分块优化

	for(ll i=1;i<=n;++i)

		scanf("%lld",&sock[i]);

	for(ll i=1;i<=m;++i)

	{

		scanf("%lld%lld",&q[i].l,&q[i].r);

		q[i].id=i;

		b[i]=(i-1)/len+1;

		ans[i].y=1;

	}

	sort(q+1,q+m+1,cmp);

	ll l=q[1].l,r=q[1].r;

	for(ll i=q[1].l;i<=q[1].r;++i)

		add(sock[i]);

	if(r-l+1!=tot)

		div(tot-(r-l+1),(q[1].r-q[1].l)*(q[1].r-q[1].l+1),q[1].id);

	for(ll i=2;i<=m;++i)

	{

		while(l<q[i].l) del(sock[l++]);

		while(l>q[i].l) add(sock[--l]);

		while(r<q[i].r) add(sock[++r]);

		while(r>q[i].r) del(sock[r--]);//暴力维护区间变化

		if(r-l+1!=tot)

			div(tot-(r-l+1),(r-l)*(r-l+1),q[i].id);

	}

	for(ll i=1;i<=m;++i)

		printf("%lld/%lld\n",ans[i].x,ans[i].y);

	return 0;

}