题解：P8330 [ZJOI2022] 众数

· · 题解

纪念肝了一下午加一晚上的题。当时一看是根分感觉这题没什么可做的，结果做起来才发现思维点和细节是真的多，这里我尽可能用浅显易懂的语言写一下。

问题可以转化为：对于任意一段区间，求区间内部众数加外部众数的和的最大值并记录外部众数的颜色可以是什么。

首先一看到众数就容易想到分块，想到分块就能自然想到根号分治，然后我们又发现了每个颜色“总和固定”的性质，就可以按照阈值 B 分治了。

在此之前，我们需要离散化，并记录每种颜色的位置作为辅助数组。设 cnt_i 为第 i 种颜色出现的次数，g_{i,j} 表示第 j 种颜色第 i 次出现在原序列的哪个位置。

首先大于 B 的显然好想一些，假设这种颜色为 x。我们枚举一种颜色 y，然后分两种情况讨论：

如果当前颜色在中间，枚举的颜色在外面，我们就可以把前缀和式子列出来：设枚举的颜色左右端点为 l,r，同时用 pre_{i,j} 表示原序列中前 i 个数有多少个 j，当前颜色的贡献区间位于 [g_l+1,g_r-1]，就可以得到式子 ans=max(ans,cnt_y-(r-l-1)+pre_{g_r,x}-pre_{g_l,x})。而后面这个式子可以转化为 cnt_y+(pre_{g_r,x}-(r-1))+(l-pre_{g_l,x})。此时我们记录前缀的 (l-pre_{g_l,x}) 最大值就可以了。

如果当前颜色在中间，枚举的颜色在外面，不难发现新式子就是上面的式子反过来：ans=max(ans,pre_{n,x}+(r-l+1)-pre_{g_r,x}+pre_{g_l,x})，转化一下就得到 pre_{n,x}+(r-pre_{g_r,x})+(pre_{g_l,x}-(l-1))。我们记录前缀 (pre_{g_l,x}-(l-1)) 最大值就可以。

这里我们一种颜色的操作次数相当于累计每种颜色的出现次数和，也就是 O(n)。而满足这个条件的颜色不超过 \frac{n}{B} 个，那么时间复杂度就是 O(\frac{n^2}{B})。

对于前缀和，我们可以只用一个数组，每次用完清空即可。

这样我们就更新了大于 B 的部分，难点在于拆式子，建议自己推一下。

然后我们考虑小于等于 B 的部分，我们考虑到前面的部分可以更新其中一种颜色次数大于 B 的部分，那么这种情况只需要考虑两者都小于 B 了。因此我们枚举外侧众数，去找内侧众数的出现次数就可以。

小范围部分常用预处理，而我们需要预处理的就是：从第 i 个数往前找，如果第一次找到一个数出现了 k 次，我们就记录这个位置为 f_{k,i}。显然对于一个 i，随着 k 减小，f_{k,i} 单调递增。

我们需要充分利用这个性质。每次枚举当前颜色 x 的一个位置 i，先设中间众数的出现次数 num 为 lim，然后在 i 的左侧从左到右枚举 j。然后我们减小 num 直到 f_{num,g_{i,x}}> g_{j,x}。这样我们就可以用 cnt_x-(i-j-1)+num 来更新答案。

设这部分的平均块长为 C，那么时间复杂度应该是 O(C^2\frac{n}{C})=O(nC)<O(nB)。我们取 B=\sqrt n，那么总时间复杂度就是 O(n\sqrt n)。

最后再考虑一种情况，就是外层众数出现在内层众数的一侧的情况。我们预处理前后缀众数的出现次数并正向和反向分别扫一遍即可。

我们把几部分合到一起就做完了这个题。记得清空。细节不少，建议放平心态认真写。


#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
#define INF 2e9
using namespace std;

int T,n,lim,m,ans,a[200005],a2[200005],to[200005],in[200005];
vector<int> g[200005],an;

void update(int nans,int p){
    if(nans>ans){
        for(auto i:an)in[i]=0;an.clear();
        an.push_back(p);ans=nans;in[p]=1;
    }
    else if(nans==ans){
        if(!in[p])an.push_back(p);in[p]=1;
    }
}

void lsh(){
    for(int i=1;i<=n;i++)a2[i]=a[i];
    sort(a2+1,a2+n+1);int len=unique(a2+1,a2+n+1)-a2-1;
    for(int i=1;i<=n;i++){
        int num=lower_bound(a2+1,a2+len+1,a[i])-a2;
        to[num]=a[i];a[i]=num;
    }
}

int num[200005],pos[200005],pre[200005],top;
void work(int x,int y){
    top=0;int sz=g[x].size();
    for(auto i:g[y])num[++top]=i;
    int maxn=pre[num[1]-1],res=0;
    for(int i=1;i<=top;i++){
        int now=i-pre[num[i]];
        res=max(res,pre[n]+maxn+now);
        maxn=max(maxn,pre[num[i]]-(i-1));
    }
    update(res,x);
    maxn=0;res=0;
    for(int i=1;i<=top;i++){
        int now=pre[num[i]]-(i-1);
        res=max(res,top+maxn+now);
        maxn=max(maxn,i-pre[num[i]]);
    }
    update(res,y);
}

int f[450][200005],lst[200005],ps[200005];
int pz[200005],sz[200005],cnt[200005];//处理前缀/后缀众数

void solve(){
    lsh();ans=0;lim=sqrt(n);
    for(int i=1;i<=n;i++)g[a[i]].push_back(i);
    for(int i=1;i<=n;i++){
        lst[i]=ps[a[i]];ps[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i,cnt=1;cnt<=lim;j=lst[j],cnt++){
            f[cnt][i]=max(f[cnt][i-1],j);
            //更新出来每个点左侧第一个出现k次数的位置
        }
    } 
    int maxn=0;
    for(int i=1;i<=n;i++)cnt[i]=0;
    for(int i=1;i<=n;i++){
        cnt[a[i]]++;if(cnt[a[i]]>maxn)maxn=cnt[a[i]];
        pz[i]=maxn;
    }
    for(int i=1;i<=n;i++)cnt[i]=0;
    maxn=0;
    for(int i=n;i>=1;i--){
        cnt[a[i]]++;if(cnt[a[i]]>maxn)maxn=cnt[a[i]];
        sz[i]=maxn;
    }//更新前后缀众数
    maxn=0;
    for(int i=1;i<=n;i++){
        if(!g[i].size())continue;
        m=0;for(auto j:g[i])pos[++m]=j;
        update(g[i].size(),i);
        if(g[i].size()>lim){
            for(int j=1;j<=n;j++)pre[j]=0;
            for(int j=1;j<=m;j++)pre[pos[j]]++;
            for(int j=1;j<=n;j++)pre[j]+=pre[j-1];
            for(int j=1;j<=n;j++){
                if(i!=j&&g[j].size())work(i,j);
            }
        }
        if(g[i].size()<=lim){
            for(int j=2;j<=m;j++){
                for(int k=1,cnt=lim;k<j;k++){
                    while(f[cnt][pos[j]-1]<=pos[k]&&cnt>=1)cnt--;
                    if(k+1==j)maxn=max(maxn,pos[j]-pos[k]);
                    update(cnt+k+(m-j+1),i);
                }
            }
        }
        for(int j=1;j<=m;j++)update((m-j+1)+pz[pos[j]-1],i);
        for(int j=m;j>=1;j--)update(j+sz[pos[j]+1],i);
    }
    cout<<ans<<"\n";sort(an.begin(),an.end());
    for(auto i:an)cout<<to[i]<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        solve();
        for(int i=0;i<=n+2;i++){
            g[i].clear();lst[i]=0;ps[i]=0;
            an.clear();in[i]=0;cnt[i]=0;a2[i]=0;
            for(int j=1;j<=lim;j++)f[j][i]=0;
            pre[i]=0;pos[i]=0;pz[i]=0;sz[i]=0;to[i]=0;num[i]=0;
        }
    }
}