今天来学了下莫队…这题应该就是这个算法的出处了

一篇别人的blog：https://www.cnblogs.com/Paul-Guderian/p/6933799.html

题意：一个序列，$m$次询问：求区间$[l,r]$内随机选出两条袜子（不放回去）颜色相同的概率，保留最简分数，$m,n,col \leq 50000$

---

对于一个询问$[l,r]$，分母为$(r-l+1)*(r-l)$，分子为$\sum_{i} (sum[col[i]])^2-(r-l+1)$，其中$sum[col[i]]$表示当前区间里颜色为$col[i]$的袜子的总数，由于不放回去我们还要减掉$r-l+1)$，于是$ans_{l,r}=\frac{\sum_{i} sum[col[i]] - (r-l+1)}{(r-l+1)*(r-l)}$

暴力统计$O(nm)$光荣TLE~

先脑补一下线段树，颜色范围太大存不下，然后好像我们没有什么办法了。

好了我编不下去了，这里直接请出我们的主角：莫队算法

我们发现如果已经得到一个区间$[l,r]$的答案可以$O(1)$算出$[l-1,r],[l+1,r],[l,r-1],[l,r+1]$的答案，重排下询问顺序可以做到$O(n \sqrt{n})$的复杂度。

具体的上面那篇blog里已经说的很详细了。

嗯代码。

其实一开始的$[l,r]$只要$r=l-1$就行了（刚好是空区间），所以我这里直接选第一个要解决的询问了

#include
#include
#include
#define rep(i,n) for(register int i=1;i<=n;i++) using namespace std; typedef long long lint; const int N=50005; inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
return s*f;
}
struct query
{
lint l,r,a,b,idx;
}q[N];
int n,m,block,s;
int belong[N],col[N],sum[N];

inline bool cmp1(const query &x,const query &y)
{
if(belong[x.l]==belong[y.l])return x.rq[i].l)modify(l-1,1),l--;
while(rq[i].r)modify(r,-1),r--;
q[i].a=s-(r-l+1);
q[i].b=1ll*(r-l)*(r-l+1);
lint t=gcd(q[i].a,q[i].b);
q[i].a/=t;q[i].b/=t;
}
sort(q+1,q+m+1,cmp2);
rep(i,m)printf("%lld/%lld\n",q[i].a,q[i].b);
return 0;
}