《算法竞赛进阶指南》0x44分块 莫队算法 小Z的袜子

题目链接：https://www.acwing.com/problem/content/description/253/

题目给出一个序列和M次询问，问从[L,R]区间中取出颜色相同的袜子的概率，实际上就是计算组合数，由于询问的数量过于庞大，只能用离线的莫队算法进行求解。

对询问进行分块，先按照l进行排序，进行分块之后对每个分块中的部分按照r进行排序，这样就使得一个块中的询问完成后右端点最多合计移动了N，左端点最多在sqrt(N)范围内移动，所以可以在O(N*sqrt(N))时间内求出所有的询问对应的值，在询问中需要设置询问的编号，因为之后需要对他进行排序。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn = 50010;
typedef long long ll;
struct node{
    int l,r,id;
}query[maxn];
ll Ans[maxn][2];
int c[maxn],L[maxn],R[maxn];
int num[maxn];
int n,m;
ll ans;
bool cmp0(node& a,node& b){//按照l进行排序 
    return a.l<b.l || (a.l==b.l && a.r<b.r);
}
bool cmp1(node& a,node& b){//块内按照r进行排序 
    return a.r<b.r;
}
void work(int x,int c){
    ans-=(ll)num[x]*(num[x]-1);
    num[x]+=c;
    ans+=(ll)num[x]*(num[x]-1);
}
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&query[i].l,&query[i].r);
        query[i].id=i;
    }
    sort(query+1,query+m+1,cmp0);
    int t=sqrt(m);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*t+1;
        R[i]=i*t;
    }
    if(R[t]<m){
        L[t+1]=R[t]+1;
        R[++t]=m;
    }
    for(int i=1;i<=t;i++){//分块内部按照r递增排序，使得每个分块內的查询时间复杂度是O(N) 
        sort(query+L[i],query+R[i]+1,cmp1);
    }
    
    for(int i=1;i<=t;i++){
        memset(num,0,sizeof(num));
        ans=0;
        int l=query[L[i]].l,r=query[L[i]].r;
        for(int j=l;j<=r;j++)work(c[j],1);//每个块中第一个单独考虑 
        Ans[query[L[i]].id][0]=ans;
        Ans[query[L[i]].id][1]=(ll)(r-l)*(r-l+1);
        ll g=gcd(Ans[query[L[i]].id][0],Ans[query[L[i]].id][1]);
        if(l==r){//只要不是两个都是0，gcd都不会是0 
            Ans[query[L[i]].id][0]=0;
            Ans[query[L[i]].id][1]=1;
        }else{
            Ans[query[L[i]].id][0]/=g;
            Ans[query[L[i]].id][1]/=g;
        }
        
        for(int j=L[i]+1;j<=R[i];j++){
            while(r<query[j].r)work(c[++r],1);
            while(r>query[j].r)work(c[r--],-1);
            while(l>query[j].l)work(c[--l],1);
            while(l<query[j].l)work(c[l++],-1);
            
            if(query[j].l==query[j].r){
                Ans[query[j].id][0]=0;
                Ans[query[j].id][1]=1;
            }else{
                Ans[query[j].id][0]=ans;
                Ans[query[j].id][1]=(ll)(r-l)*(r-l+1);
                ll g=gcd(Ans[query[j].id][0],Ans[query[j].id][1]);
                Ans[query[j].id][0]/=g;
                Ans[query[j].id][1]/=g;
            }
        }
    }
    
    for(int i=1;i<=m;i++){
        printf("%lld/%lld
",Ans[i][0],Ans[i][1]);
    }
    return 0;
}