题解：P13984 数列分块入门 9

· · 题解

一个区间的众数显然只有两种情况：

  1. 存在于左右散块。
  2. 中间整块的众数。

我们先把序列离散化，然后对于每个数开一个 vector 记录位置。

对于每两个块，记录从左侧块开始到右侧块结束之间的众数。时间复杂度 O(n\sqrt n)。

对于每次查询，我们先暴力查询左右散块每个值在区间内出现的次数，与中间的所有整块的众数出现次数相比较，最多的那个就是区间众数。

离散化写的是错的，不要抄（但是能过）。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+1;
int n,cnt,q,x,y,k,a[N],f[N],dp[1001][1001],c[N],bel[N],L[N],R[N],lz[N],blo;
vector<int>C[N];
unordered_map<int,int>d;
int count(int l,int r,int k){
    return upper_bound(C[k].begin(),C[k].end(),y)-lower_bound(C[k].begin(),C[k].end(),x);
}
void build(int n){
    blo=sqrt(n);
    cnt=(n+blo-1)/blo;
    for(int i=1;i<=cnt;i++){
        L[i]=(i-1)*blo+1;
        R[i]=i*blo;
    }
    R[cnt]=n;
    for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
}
int qmax(int x,int y){
    int ans=0,b=1e18,p;
    if(bel[x]==bel[y]){
        memset(c,0,sizeof c);
        for(int i=x;i<=y;i++){
            c[a[i]]++;
            if(ans<c[a[i]]) ans=c[a[i]],b=a[i];
            else if(ans==c[a[i]]) b=min(b,a[i]);
        }
        return b;
    }
    for(int i=x;i<=R[bel[x]];i++){
        p=count(x,y,a[i]);
        if(p>ans) ans=p,b=a[i];
        else if(p==ans) b=min(b,a[i]);
    }
    for(int i=L[bel[y]];i<=y;i++){
        p=count(x,y,a[i]);
        if(p>ans) ans=p,b=a[i];
        else if(p==ans) b=min(b,a[i]);
    }
    p=count(x,y,dp[bel[x]+1][bel[y]-1]);
    if(p>ans) ans=p,b=dp[bel[x]+1][bel[y]-1];
    else if(p==ans) b=min(b,dp[bel[x]+1][bel[y]-1]);
    return b;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    q=n;
    for(int i=1;i<=n;i++) cin>>a[i],f[i]=a[i];
    build(n);
    sort(f+1,f+1+n);
    for(int i=1;i<=n;i++) d[f[i]]=i;
    for(int i=1;i<=n;i++) a[i]=d[a[i]];
    for(int i=1;i<=n;i++) C[a[i]].push_back(i);
    for(int i=1;i<=cnt;i++){
        memset(c,0,sizeof c);
        int b=1e18,ans=0;
        for(int j=i;j<=cnt;j++){
            for(int k=L[j];k<=R[j];k++){
                c[a[k]]++;
                if(c[a[k]]>ans) ans=c[a[k]],b=a[k];
                else if(c[a[k]]==ans) b=min(b,a[k]);
            }
            dp[i][j]=b;
        }
    }
    while(q--){
        cin>>x>>y;
        cout<<f[qmax(x,y)]<<'\n';
    }
}