题解：P13984 数列分块入门 9

· · 题解

本题没有修改，这类题目可以预处理出每两个块之间的答案来解决整块问题。

分块，令块长为 B，块数 T=\frac{n}{B}。

首先离散化。一个区间的众数可能是所有整块的众数，也可能是散块中的数。

对于整块，可以直接预处理出从某个整块开始到另一个整块结束这一段区间的众数。具体的，从每个块的开始向后枚举，暴力维护每种数出现次数来动态维护当前最小众数，在每个块的末尾记录答案即可。时间复杂度 O(nT)。

散块中的所有数都有可能成为众数，考虑维护每个数在一个区间内出现次数。具体的，对每种数都开一个动态数组，查询一个区间时，直接找出对应的动态数组再用二分等方法即可快速求出有多少这种数在区间内。单次查询次数时间复杂度 O(\log n)，有 n 次询问每次有 B 个散块点。时间复杂度 O(Bn\log n)。

查询时若全为散块直接暴力即可。若有整块先找出所有整块的众数并算出出现次数，散块部分查询次数更新答案。

进行时间复杂度平衡，即令 nT=Bn\log n。推导可得 B=\sqrt \frac{n}{\log n}，时间复杂度 O(n\sqrt {n\log n})。

代码实现难度较低，建议初学者练习。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<ctime>
#include<random>
#define ll long long
using namespace std;
inline int read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=3e5+10;
const int B=128;
const int T=N/B+10;
int n,a[N],b[N],c[N],d[N];
int L[N],R[N],pos[N];
int sum[T][T];
vector<int>A[N];
int get(int x,int l,int r){
    return upper_bound(A[x].begin(),A[x].end(),r)-lower_bound(A[x].begin(),A[x].end(),l);
}
int id,res;
void upd(int p,int s){
    if(s>res||(s==res&&p<id))
        id=p,res=s;
}
int query(int l,int r){
    int p=pos[l],q=pos[r];
    id=0,res=0;
    if(p==q){
        for(int i=l;i<=r;i++){
            c[a[i]]++;
            upd(a[i],c[a[i]]);
        }
        for(int i=l;i<=r;i++)
            c[a[i]]=0;
        return id;
    }
    if(p+1<=q-1)upd(sum[p+1][q-1],get(sum[p+1][q-1],l,r));
    for(int i=l;i<=R[p];i++)
        upd(a[i],get(a[i],l,r));
    for(int i=L[q];i<=r;i++)
        upd(a[i],get(a[i],l,r));
    return id;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        b[i]=a[i]=read();
    sort(b+1,b+n+1);
    int s=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+s+1,a[i])-b;
        A[a[i]].push_back(i);
    }
    int t=n/B;
    for(int i=1;i<=t;i++){
        L[i]=R[i-1]+1;
        R[i]=R[i-1]+B;
    }
    if(R[t]<n){
        t++;
        L[t]=R[t-1]+1;
        R[t]=n;
    }
    for(int i=1;i<=t;i++)
        for(int j=L[i];j<=R[i];j++)
            pos[j]=i;
    for(int i=1;i<=t;i++){
        int id=0;
        for(int p=i;p<=t;p++){
            for(int j=L[p];j<=R[p];j++){
                c[a[j]]++;
                if(c[a[j]]>c[id]||(c[a[j]]==c[id]&&a[j]<id))
                    id=a[j];
            }   
            sum[i][p]=id;
        }
        for(int j=1;j<=n;j++)
            c[j]=0;
    }
    for(int i=1;i<=n;i++){
        int l=read(),r=read();
        printf("%d",b[query(l,r)]);
        putchar('\n');
    }
    return 0;
}