题解：P13984 数列分块入门 9

· · 题解

分块好题（确信）。

这次就先放代码，然后慢慢讲解（本人也刚学会）。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
const int N=550;
int a[N*N],b[N*N],ans[N<<1][N<<1],pre[N][N*N],cnt[N*N];
int n,blk;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i],b[i]=a[i];
    }
    sort(b,b+n);
    int len=unique(b,b+n)-b;
    for(int i=0;i<n;i++){
        a[i]=lower_bound(b,b+len,a[i])-b;
    }
    blk=sqrt(n);
    for(int i=0;i<(n-1)/blk+1;i++){
        memset(cnt,0,sizeof (int)*n);
        int Cnt=0,Min=0;
        for(int j=i*blk;j<n;j++){
            cnt[a[j]]++;
            if(cnt[a[j]]>Cnt||(cnt[a[j]]==Cnt&&a[j]<Min)){
                Cnt=cnt[a[j]],Min=a[j];
            }
            if((j+1)%blk==0||j+1==n) ans[i][j/blk]=Min;
        }
    }
    memset(cnt,0,sizeof (int)*n);
    for(int i=0;i<n;i++){
        for(int j=i/blk;j<(n-1)/blk+1;j++){
            pre[j][a[i]]++;
        }
    }
    for(int T=1;T<=n;T++){
        int l,r;cin>>l>>r;
        l--,r--;
        int Min=0,Cnt=0;
        if(l/blk==r/blk){
            for(int i=l;i<=r;i++){
                cnt[a[i]]++;
                if(cnt[a[i]]>Cnt||(cnt[a[i]]==Cnt&&a[i]<Min)){
                    Cnt=cnt[a[i]],Min=a[i];
                }
            }
            for(int i=l;i<=r;i++) cnt[a[i]]--;
        }
        else{
            for(int i=l;i<(l/blk+1)*blk;i++){
                cnt[a[i]]++;
                int U=pre[r/blk-1][a[i]]-pre[l/blk][a[i]]+cnt[a[i]];
                if(U>Cnt||(U==Cnt&&a[i]<Min)){
                    Cnt=U,Min=a[i];
                }
            }
            for(int i=r/blk*blk;i<=r;i++){
                cnt[a[i]]++;
                int U=pre[r/blk-1][a[i]]-pre[l/blk][a[i]]+cnt[a[i]];
                if(U>Cnt||(U==Cnt&&a[i]<Min)){
                    Cnt=U,Min=a[i];
                }
            }
            if(r/blk-l/blk>1){
                int f=ans[l/blk+1][r/blk-1];
                int U=pre[r/blk-1][f]-pre[l/blk][f];
                if(U>Cnt||(U==Cnt&&f<Min)){
                    Cnt=U,Min=f;
                }
            }
            for(int i=l;i<(l/blk+1)*blk;i++) cnt[a[i]]--;
            for(int i=r/blk*blk;i<=r;i++) cnt[a[i]]--;
        }
        cout<<b[Min]<<'\n';
    }
    return 0;
}

:::

1. 离散化

这么大的值域，当然要离散化了。

for(int i=0;i<n;i++){
    cin>>a[i],b[i]=a[i];
}
sort(b,b+n);
int len=unique(b,b+n)-b;
for(int i=0;i<n;i++){
    a[i]=lower_bound(b,b+len,a[i])-b;
}

将数值转换为编号，方便处理（能开下数组）。

2. 预处理

预处理出块内众数，方便修改和查询。

blk=sqrt(n);
for(int i=0;i<(n-1)/blk+1;i++){
    memset(cnt,0,sizeof (int)*n);
    int Cnt=0,Min=0;
    for(int j=i*blk;j<n;j++){
        cnt[a[j]]++;
        if(cnt[a[j]]>Cnt||(cnt[a[j]]==Cnt&&a[j]<Min)){
            Cnt=cnt[a[j]],Min=a[j];
        }
        if((j+1)%blk==0||j+1==n) ans[i][j/blk]=Min;
    }
}

搜到一个块的结束，记录答案。

3. 前缀和

当然是数的出现次数的前缀和了。

memset(cnt,0,sizeof (int)*n);
for(int i=0;i<n;i++){
    for(int j=i/blk;j<(n-1)/blk+1;j++){
        pre[j][a[i]]++;
    }
}

先卖个关子，以后会用到。

4. 查询

重头戏来了。

在同一块内

int Min=0,Cnt=0;
if(l/blk==r/blk){
    for(int i=l;i<=r;i++){
        cnt[a[i]]++;
        if(cnt[a[i]]>Cnt||(cnt[a[i]]==Cnt&&a[i]<Min)){
            Cnt=cnt[a[i]],Min=a[i];
        }
    }
    for(int i=l;i<=r;i++) cnt[a[i]]--;
}

直接暴力统计出现次数，修改众数。

不在同一块内

for(int i=l;i<(l/blk+1)*blk;i++){
    cnt[a[i]]++;
    int U=pre[r/blk-1][a[i]]-pre[l/blk][a[i]]+cnt[a[i]];
    if(U>Cnt||(U==Cnt&&a[i]<Min)){
        Cnt=U,Min=a[i];
    }
}
for(int i=r/blk*blk;i<=r;i++){
    cnt[a[i]]++;
    int U=pre[r/blk-1][a[i]]-pre[l/blk][a[i]]+cnt[a[i]];
    if(U>Cnt||(U==Cnt&&a[i]<Min)){
        Cnt=U,Min=a[i];
    }
}
//左右散块
if(r/blk-l/blk>1){
    int f=ans[l/blk+1][r/blk-1];
    int U=pre[r/blk-1][f]-pre[l/blk][f];
    if(U>Cnt||(U==Cnt&&f<Min)){
        Cnt=U,Min=f;
    }
}
//中间整块
for(int i=l;i<(l/blk+1)*blk;i++) cnt[a[i]]--;
for(int i=r/blk*blk;i<=r;i++) cnt[a[i]]--;

对于左右的散块，直接暴力，次数前缀和的作用就体现出来了；而中间的整块就用之间预处理出来的区间众数统计即可。
最后输出答案即可。

注意：这里的 Min 为离散化后的下标，不要直接输出。

QwQ，感谢看完。