题目：    链接：https://www.luogu.org/problemnew/show/P1494

                题意：一些袜子排成一排，每个袜子有固定的颜色。

                          每次询问在[l,r]的袜子中等概率选两只，求有多大的概率抽到两只一样颜色的。

 

思路： 其实 就是 求     莫队维护 一波 cnt[ i ] * cnt[ i ]    就是模板嘛

 

 

#include
      
       #define LL long longusing namespace std;int c[500005],pos[500005];LL num[500005],up[500005],dw[500005],ans,u,v,w;struct note {    int l,r,id;}a[500005];bool cmp(note uu,note vv) {    if(pos[uu.l]==pos[vv.l]) return uu.r
       
        a[i].r;j--) updat(j,-1);        }        r=a[i].r;        if(l
        
         =a[i].l;j--) updat(j,1);        }        l=a[i].l;        u=ans-a[i].r+a[i].l-1;        v=(LL)(a[i].r-a[i].l+1)*(a[i].r-a[i].l);        w=__gcd(u,v); u/=w; v/=w; up[in]=u; dw[in]=v;    }    for(int i=1;i<=q;i++) printf("%lld/%lld\n",up[i],dw[i]);    return 0;}