BZOJ2038 [2009国家集训队]小Z的袜子(hose)

https://www.lydsy.com/JudgeOnline/problem.php?id=2038
题意：给定长为n的区间，每个点有一只袜子，每只袜子有一个颜色。给定m次询问，每次询问是：求在[L,R]区间任选两只袜子，它们颜色相同的概率。
思路：普通莫队的经典题。
每次询问的答案是： $\frac{{\sum }_{color=1}^n{C}_{cnt\left(color\right)}^2}{C_{r-l+1}^2}，分母就是\frac{(r-l+1)\ast (r-l)}{2}，分子变形=\sum \frac{cnt\left(color\right)\ast \left(cnt\right(color)-1)}{2}=\sum \frac{cn{t}^2\left(color\right)-cnt\left(color\right)}{2},\sum cnt\left(color\right)=r-l+1,具体见下面的链接吧，我就不造轮子了。。。$Cr−l+12​∑color=1n​Ccnt(color)2​​，分母就是2(r−l+1)∗(r−l)​，分子变形=∑2cnt(color)∗(cnt(color)−1)​=∑2cnt2(color)−cnt(color)​,∑cnt(color)=r−l+1,具体见下面的链接吧，我就不造轮子了。。。
http://www.cnblogs.com/hzf-sbit/p/4056874.html
这篇博客对于这道题和莫队的时间复杂度都分析的很好。
提炼一下就是这几句话：在https://blog.sengxian.com/algorithms/mo-s-algorithm这篇blog

有一点要注意的地方，区间移动时最好先扩后缩，否则可能会出现[5,3]这样的不合法的区间。

#include<bits/stdc++.h>
using namespace std;
#define maxn 50000+100
#define ll long long

int n,m,c[maxn],cnt[maxn],SIZE;
ll ans[maxn],num[maxn],now_ans;

struct query{
    int l,r,idx;
    bool operator < (query x)const{
        if(l/SIZE != x.l/SIZE)return l/SIZE < x.l/SIZE;
        return r < x.r;
    }
}Q[maxn];

void move(int p,int flag)
{
    if(flag==1){    
        now_ans+=2*cnt[c[p]];
        cnt[c[p]]++;
    }else{
        now_ans+=2-2*cnt[c[p]];
        cnt[c[p]]--;
    }
}

int main()
{
   // freopen("input.in","r",stdin);
    cin>>n>>m;
    SIZE=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=m;i++)scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].idx=i,num[i]=(ll)(Q[i].r-Q[i].l+1)*(Q[i].r-Q[i].l);
    sort(Q+1,Q+1+m);
    int l=Q[1].l,r=l-1;
    for(int i=1;i<=m;i++)
    {   
        while(l>Q[i].l)move(--l,1);
        while(r<Q[i].r)move(++r,1);
        while(l<Q[i].l)move(l++,-1);
        while(r>Q[i].r)move(r--,-1);
        ans[Q[i].idx]=now_ans;
    }   
    for(int i=1;i<=m;i++)
    {
        int gcd=__gcd(num[i],ans[i]);
        printf("%lld/%lld\n",ans[i]/gcd,num[i]/gcd);
    }
    return 0;
}