题解：P13984 数列分块入门 9

· · 题解

前言

洛谷终于有分块模板啦！

思路

由于众数不满足“区间可加性”，因此难以用线段树或者树状数组进行维护，所以考虑分块。

先考虑整块。用 m_{i,j} 表示第 i 块到第 j 块的区间众数。枚举左块，然后向右拓展每一个数，然后看一下当前拓展的数出现次数是否为最大的，如果是，则更新左块到当前拓展的数所在块的答案。复杂度 O(n\sqrt n)。

此时的众数可能来自三个地方：左边散块，中间整块，右边散块。中间很好搞，上一段已预处理，散块呢？考虑到散块大小不超过 \sqrt n，所以我完全可以暴力算散块中每个数在整个区间的出现次数，最后三个地方取最大值即可。复杂度 O(\sqrt n)。

最后不要忘了离散化。

代码

#include<bits/stdc++.h>//代码有些丑陋
using namespace std;
const int N=3e5+5;
int a[N],sum[1001][N],m[1001][1001],cnt[N];
int pos[N],b[N],L[1001],R[1001];
int n;
int len;
void init()
{
    int t=sqrt(n);
    for(int i=1;i<=t;i++)
    {
        L[i]=R[i-1]+1;
        R[i]=i*t;
    }
    if(R[t]<n)
    {
        t++;
        R[t]=n;
        L[t]=R[t-1]+1;
    }
    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++)
    {
        for(int j=1;j<=len;j++) sum[i][j]=sum[i-1][j];//表示前i块j出现次数，以便后面查询p到q块某个数出现次数
        for(int j=L[i];j<=R[i];j++)
        {
            sum[i][a[j]]++;
        }
    }
    for(int i=1;i<=t;i++)
    {
        int res=0,ans=0;
        for(int j=L[i];j<=n;j++)
        {           
            cnt[a[j]]++;
            if(cnt[a[j]]>res||(cnt[a[j]]==res&&b[a[j]]<b[ans]))//按题意取最值
            {
                res=cnt[a[j]];
                ans=a[j];
            }
            m[i][pos[j]]=ans;
        }
        memset(cnt,0,sizeof cnt);
    }   
}
int enquir(int l,int r)
{
    int t=sqrt(n);
    int p=pos[l],q=pos[r];
    int ans=m[p+1][q-1],res=max(0,sum[q-1][ans]-sum[p][ans]);
    int lim=min(R[p],r),f=0;
    if(p!=q) f=1;\\代表中间有整块
    for(int i=l;i<=lim;i++) cnt[a[i]]=max(0,sum[q-1][a[i]]-sum[p][a[i]]);
    if(f)
    {
        for(int i=L[q];i<=r;i++)
        {
            cnt[a[i]]=max(0,sum[q-1][a[i]]-sum[p][a[i]]);
        }
    }
    for(int i=l;i<=lim;i++)
    {
        cnt[a[i]]++;
        if(cnt[a[i]]>res||(cnt[a[i]]==res&&b[a[i]]<b[ans]))
        {
            ans=a[i];
            res=cnt[a[i]];
        }
    }
    if(f)
    {
        for(int i=L[q];i<=r;i++)
        {
            cnt[a[i]]++;
            if(cnt[a[i]]>res||(cnt[a[i]]==res&&b[a[i]]<b[ans]))
            {
                ans=a[i];
                res=cnt[a[i]];
            }
        }
    }
    return ans;
}
signed main()
{
//  freopen("P4168_3.in","r",stdin);
//  freopen("P4168_3.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
    init();
    int l,r,x=0;
    for(int i=1;i<=n;i++)
    {
        cin>>l>>r;
        if(l>r) swap(l,r);
        x=b[enquir(l,r)];
        cout<<x<<endl;
    }
    return 0;
}