经典的莫队
考虑一种颜色对答案的贡献 ：
设此颜色的数量为 cnt，那么有 cnt * ( cnt - 1 ) 种方案拿到两只此颜色袜子
设总数为 sum，那么一共有 sum * ( sum-1 ) 种不同的拿袜子方案
只要把所有同色的方案除以总方案就是我们的答案了
那么我们可以同时维护拿到同色的方案总数 x 和总方案数 y
设 cnt [ x ] 表示当前颜色为 x 的袜子的总数
对于一个新加入的袜子，此颜色的袜子的数量 + 1
那么原本为 cnt * ( cnt - 1 ) 的方案数变成了 ( cnt + 1 ) * cnt
相当于多了 2 * cnt （注意此时 cnt 是此袜子加入前的数量）
注意总方案数也有增加，从 sum * ( sum - 1 ) 到 ( sum + 1 ) * sum
所以要考虑对 x 和 y 的贡献
如果减少也是相同的道理，很容易推出来的
最后一定要注意 x 和 y 要开long long !
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=5e4+7; int n,m,col[N]; struct data { int l,r,id,pos; inline bool operator < (const data &tmp) const { return pos!=tmp.pos ? pos<tmp.pos : r<tmp.r; } }d[N];//存询问 int cnt[N]; ll ans[N][2],x,y; ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; }//用来约分 int main() { n=read(); m=read(); for(int i=1;i<=n;i++) col[i]=read(); int t=sqrt(n)+1; for(int i=1;i<=m;i++) { d[i].l=read(); d[i].r=read(); d[i].id=i; d[i].pos=(d[i].l-1)/t+1; } sort(d+1,d+m+1); int l=1,r=0; for(int i=1;i<=m;i++) { while(r<d[i].r) r++,x+=2*cnt[col[r]],y+=2*(r-l),cnt[col[r]]++; while(r>d[i].r) x-=2*cnt[col[r]]-2,y-=2*(r-l+1)-2,cnt[col[r]]--,r--; while(l<d[i].l) x-=2*cnt[col[l]]-2,y-=2*(r-l+1)-2,cnt[col[l]]--,l++; while(l>d[i].l) l--,x+=2*cnt[col[l]],y+=2*(r-l),cnt[col[l]]++; //注意细节 if(x)//注意特判 { ll g=gcd(x,y); ans[d[i].id][0]=x/g; ans[d[i].id][1]=y/g; } else ans[d[i].id][0]=0,ans[d[i].id][1]=1; } for(int i=1;i<=m;i++) printf("%lld/%lld ",ans[i][0],ans[i][1]); return 0; }