【传送门：】

---

简要题意：

　　给出n只袜子，每只袜子都有颜色

　　有多个询问，每次询问一个区间L,R，求出在这个区间内选出两只相同颜色袜子的概率，以最简分数形式输出（不用化成整数，如果概率为0，则输出0/1）

---

题解：

　　接触莫队第一题

　　我们先假设当前要询问的区间内第一种颜色的袜子有a只，第二种有b只......最后一种颜色的袜子有x只

　　那么我们输出的答案应该是：$ans=\frac{\frac{a(a-1)}{2}+\frac{b(b-1)}{2}+...+\frac{x(x-1)}{2}}{\frac{(R-L+1)(R-L)}{2}}$

　　我们来化简一下，得到：

　　$$ans=\frac{a(a-1)+b(b-1)+...+x(x-1)}{(R-L+1)(R-L)}$$

　　$$ans=\frac{a^2-a+b^2-b+...+x^2-x}{(R-L+1)(R-L)}$$

　　$$ans=\frac{a^2+b^2+...+x^2-(a+b+...+x)}{(R-L+1)(R-L)}$$

　　$$ans=\frac{a^2+b^2+...+x^2-(R-L+1)}{(R-L+1)(R-L)}$$

　　然后我们对它来进行莫队求解

　　最后来膜一膜

---

参考代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long LL;LL gcd(LL a,LL b){
    if(a==0) return b;return gcd(b%a,a);}struct node{    LL x,y;    int id,l,r;}a[51000];int bk[51000];bool cmp1(node n1,node n2){    return bk[n1.l]==bk[n2.l]?n1.r
          
           
            a[i].l){update(l-1,1);l--;} while(r
            
             a[i].r){update(r,-1);r--;} if(a[i].l==a[i].r){a[i].x=0;a[i].y=1;continue;} a[i].x=x-(r-l+1);a[i].y=LL(r-l+1)*LL(r-l); LL gd=gcd(a[i].x,a[i].y); a[i].x/=gd;a[i].y/=gd; } sort(a+1,a+m+1,cmp2); for(int i=1;i<=m;i++) printf("%lld/%lld\n",a[i].x,a[i].y); return 0;}