bzoj 2038 经典莫队 小z的袜子

莫队入门
小z的袜子
题意：n个数记ai，ai<=n
m次询问：l~r区间内任意选两个数 求其相同的概率
稍微化简为 求区间内每个数出现次数的平方和

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
typedef pair<LL,LL>pll;
const int maxn=1e5;
const int oo=1e9;
LL a[maxn+5],cnt[maxn+5],pos[maxn+5],n,m,L=1,R=0,Ans=0;
struct node
{
    LL l,r,id;
}b[maxn+5];
bool cmp(node a,node b)
{
    if(pos[a.l]==pos[b.l]) return a.r<b.r;
    return pos[a.l]<pos[b.l];
}
pll ans[maxn+5];
void del(int x)
{
    Ans-=cnt[a[x]]*cnt[a[x]];
    cnt[a[x]]--;
    Ans+=cnt[a[x]]*cnt[a[x]];
}
void add(int x)
{
    Ans-=cnt[a[x]]*cnt[a[x]];
    cnt[a[x]]++;
    Ans+=cnt[a[x]]*cnt[a[x]];
}
int main()
{
    scanf("%lld %lld",&n,&m);
    LL len=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),pos[i]=i/len;
    for(int i=1;i<=m;i++){
        scanf("%lld %lld",&b[i].l,&b[i].r);
        b[i].id=i;
    }
    sort(b+1,b+1+m,cmp);
    for(int i=1;i<=m;i++){
        while(L<b[i].l){
            del(L);
            L++;
        }
        while(L>b[i].l){
            L--;
            add(L);
        }
        while(R<b[i].r){
            R++;
            add(R);
        }
        while(R>b[i].r){
            del(R);
            R--;
        }
        LL x=Ans-(b[i].r-b[i].l+1);
        LL y=(b[i].r-b[i].l+1)*(b[i].r-b[i].l);
        LL gcd=__gcd(x,y);
        ans[b[i].id].first=x/gcd;
        ans[b[i].id].second=y/gcd;
    }
    for(int i=1;i<=m;i++){
        printf("%lld/%lld\n",ans[i].first,ans[i].first?ans[i].second:1);
    }
}