BZOJ 2038 小Z的袜子

题目大意

给你一堆N个袜子，M次询问求$[L,R]$区间内选出两个一样袜子的几率。

首先我们可以得出这个东西的概率是$\sum\limits_{i=l}^{R}\frac{C_i}{R-L+1}\frac{C_i-1}{R-L}$，然后分母是已知的，所以只需要维护$C_i(C_i-1)$就可以了。我们发现对于已知的$[L,R]$，得出状态$[L,R+1],[L,R-1],[L-1,R],[L+1,R]$都只需要$O(1)$的时间，所以考虑引入莫队。

简单的莫队（比如这道题）就是一种处理区间询问的暴力做法，其时间复杂度是较为优越的$O(N * sqrt{N})$.

首先将询问离线并排序，排序方法为：第一关键字是询问左端点所在块(每块大小$sqrt{N}$)编号，第二关键字是右端点。之后初始化第一次询问，对于每一次新的询问，直接从旧的答案转移就可以了。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,block,cnt[50010],c[50010];
long long ans,down;
long long gcd(long long tx,long long ty)
{
    return ty?gcd(ty,tx%ty):tx;
}
struct query
{
    int l,r,bl,id;
    long long ansx,ansy;
}q[50010];
bool cmp(query tx,query ty)
{
    if(tx.bl==ty.bl) return tx.r<ty.r;
    return tx.bl<ty.bl;
}
bool cmpb(query tx,query ty)
{
    return tx.id<ty.id;
}
void init()
{
    for(int i=q[1].l;i<=q[1].r;++i) cnt[c[i]]++;
    for(int i=1;i<=50000;++i) ans+=1ll*cnt[i]*(cnt[i]-1);
    down=1ll*(q[1].r-q[1].l)*(q[1].r-q[1].l+1);
    long long tmp=gcd(ans,down);
    q[1].ansx=ans/tmp,q[1].ansy=down/tmp;
    return;
}
void movel(int tx,int ty)
{
    if(tx<ty) for(int i=tx;i<ty;i++) ans-=1ll*(cnt[c[i]]-1)*2,cnt[c[i]]--;
    if(tx>ty) for(int i=tx-1;i>=ty;i--) ans+=1ll*cnt[c[i]]*2,cnt[c[i]]++;
}
void mover(int tx,int ty)
{
    if(tx<ty) for(int i=tx+1;i<=ty;i++) ans+=1ll*cnt[c[i]]*2,cnt[c[i]]++;
    if(tx>ty) for(int i=tx;i>ty;i--) ans-=1ll*(cnt[c[i]]-1)*2,cnt[c[i]]--;
}
int main()
{
    scanf("%d%d",&n,&m);
    block=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].bl=(q[i].l/block)+1,q[i].id=i;
    sort(q+1,q+m+1,cmp);
    init();
    for(int i=2;i<=m;++i)
    {
        mover(q[i-1].r,q[i].r);
        movel(q[i-1].l,q[i].l);
        down=1ll*(q[i].r-q[i].l)*(q[i].r-q[i].l+1);
        long long tmp=gcd(ans,down);
        q[i].ansx=ans/tmp,q[i].ansy=down/tmp;
    }
    sort(q+1,q+m+1,cmpb);
    for(int i=1;i<=m;++i) printf("%lld/%lldn",q[i].ansx,q[i].ansy);
    return 0;
}