• 莫队板子题，对询问进行排序+分块，从而得到巧妙的复杂度
• 对于L,R的询问。

  设其中颜色为x,y,z的袜子的个数为a,b,c...

  那么答案即为 (a*(a-1)/2+b*(b-1)/2+c*(c-1)/2....)/((R-L+1)*(R-L)/2)(a∗(a−1)/2+b∗(b−1)/2+c∗(c−1)/2....)/((R−L+1)∗(R−L)/2)

  化简得: (a^2+b^2+c^2+...x^2-(a+b+c+d+.....))/((R-L+1)*(R-L))(a2+b2+c2+...x2−(a+b+c+d+.....))/((R−L+1)∗(R−L))

  即： (a^2+b^2+c^2+...x^2-(R-L+1))/((R-L+1)*(R-L))(a2+b2+c2+...x2−(R−L+1))/((R−L+1)∗(R−L))

  我们需要解决的一个问题

  求一个区间内每种颜色数目的平方和。

• 代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;#define res register intinline int read(){	int x(0),f(1); char ch;	while(!isdigit(ch=getchar())) if(ch=='-') f=-1;	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();	return f*x;}const int N=50005;struct node{int x,y,z;LL p,q;}a[N];int pos[N],c[N];LL cnt[N];int n,m,block;inline bool cmp1(const node &n1,const node &n2){	if(pos[n1.x]==pos[n2.x]) return n1.y
          
           a[i].y ; --r) update(r,-1); for( ; l
           
            a[i].x ; --l) update(l-1,1); LL len=a[i].y-a[i].x+1; a[i].p=ans-len; a[i].q=len*(len-1); LL tmp=gcd(a[i].p,a[i].q); a[i].p/=tmp; a[i].q/=tmp; }}int main(){ n=read(); m=read(); for(res i=1 ; i<=n ; ++i) c[i]=read(); for(res i=1 ; i<=m ; ++i) a[i].x=read(),a[i].y=read(),a[i].z=i; block = sqrt(n); for(res i=1 ; i<=n ; ++i) pos[i]=(i-1)/block+1; sort(a+1,a+m+1,cmp1); solve(); sort(a+1,a+m+1,cmp2); for(res i=1 ; i<=m ; ++i) printf("%lld/%lld\n",a[i].p,a[i].q); return 0;}