似乎是莫队提出莫队的题目？

原题：

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

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

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

N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

 

恩莫队裸题，分块排序什么的就不说了，关键在于O(1)转移答案

用的比较多的方法是每种颜色重复数平方的和减去区间长度为分子，区间长度*(区间长度-1)为分母（最后gcd搞一下）

我想不明白问什么，求教数学大神syq，syq大神太神辣

首先先直接写出公式，设第i种颜色重复数为a[i]，左端点l，右端点r，则答案为( a[i]*(a[i]-1)+a[i+1]*(a[i+1]-1)+…… )/(r-l+1)*(r-l)

整理分子可以得到(a[i]*a[i] + a[i+1]*a[i+1]+……-a[i]-a[i+1]-……)

所有a的总和等于区间长度，-a[i]-a[i+1]-……就可以写成-(r-l+1)

所以最终答案表示为( a[i]*a[i] + a[i+1]*a[i+1]+……-(r-l+1) )/(r-l+1)*(r-l)

每次l和r左右移动的时候维护a[i]*a[i]的和即可

果然遇到数学相关还是要尝试推一下吗，一个思路是将复杂的其它量整合成简单的已知量？

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 #define ll long long 9 int rd(){ int z=0,mk=1; char ch=getchar();10 while(ch<'0'||ch>'9'){ if(ch=='-')mk=-1; ch=getchar();}11 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();}12 return z*mk;13 }14 ll gcd(ll x,ll y){ return y?gcd(y,x%y):x;}15 inline ll sqr(ll x){ return x*x;}16 struct dcd{ int l,r,id;}b[51000];17 int n,m,a[51000]; int blck;18 int cnt[51000];19 ll bwl=0,x[51000],y[51000];20 inline void mdf(int x,int y){ bwl-=sqr(cnt[a[x]]),cnt[a[x]]+=y,bwl+=sqr(cnt[a[x]]);}21 bool cmp(dcd x,dcd y){ return (x.l/blck==y.l/blck)?(x.r
            
             >n>>m; blck=(int)sqrt(n*1.0);24 for(int i=1;i<=n;++i) a[i]=rd();25 for(int i=1;i<=m;++i) b[i].l=rd(),b[i].r=rd(),b[i].id=i;26 sort(b+1,b+m+1,cmp);27 int l=1,r=0;28 for(int i=1;i<=m;++i){29 while(l
             
              b[i].l) mdf(l-1,1),--l;31 while(r
              
               b[i].r) mdf(r--,-1);33 x[b[i].id]=bwl-(b[i].r-b[i].l+1);34 y[b[i].id]=(ll)(b[i].r-b[i].l+1)*(b[i].r-b[i].l);35 int ggcd=gcd(x[b[i].id],y[b[i].id]);36 x[b[i].id]/=ggcd,y[b[i].id]/=ggcd;37 }38 for(int i=1;i<=m;++i) printf("%lld/%lld\n",x[i],y[i]);39 return 0;40 }