题解：P8330 [ZJOI2022] 众数

dyc2022 · 2025-07-25 20:01:57 · 题解

更好的阅读体验

感觉这题真的很难（写）吧！

问题可以认为是：选定一个区间 [l,r]，求 [l,r] 的众数和 [l,r] 外的众数出现次数和的最大值。

众数和出现次数密切相关，而所有数字出现次数之和恰好为 n，因此我们能够想到根号分治。

取 B = \sqrt{n}，由此，我们可以把数字按照出现次数 \ge B 和 < B 分成两类，前者的数字至多有 \sqrt{n} 个，后者每个数的出现次数至多为 \sqrt{n}。

因此可以衍生出两个做法。

枚举区间众数 x。

• 当 x 出现次数 \ge B，那么枚举区间外众数 y。构造序列 s，钦定 a_i=x 的位置是 s_i=1，a_i= y 的位置是 s_i=-1，求出该序列抠掉一个区间后的和的最大值。显然我们把左右端点设置在 s_i=1 的位置一定不劣。所以可以枚举右端点，对左端点尺取。由于对于所有的数字，满足条件的右端点数量之和为 O(n)，而尺取的两端点的总位移为 O(n)，因此这部分的复杂度为 O(n \sqrt{n})。
• 当 x 出现次数 <B，那么枚举 x 的出现次数 k，同时预处理出 i 前面第 k 个和 i 值一样的位置 \text{pre}_i，这时直接枚举右端点，用类似第一种情况的尺取法取左端点即可完成。出现次数最多 O(n\sqrt{n})，左右端点都是 O(n) 次移动，因此这部分复杂度为 O(n \sqrt{n})。

这样综合起来，总复杂度就是 O(n \sqrt{n})。

::::info[代码]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 200006
using namespace std;
void chkmax(int &x,int y){x=x<y?y:x;}
int T,n,B,bn,maxn,maxcur,o;
int a[N],b[N],cnt[N],sum[N],ans[N],rk[N],pre[N];
vector<int> vec[N],va,vb;
void solve_a()
{
    for(int v:va)
    {
        for(int i=1;i<=n;i++)sum[i]=0;
        for(int i:vec[v])sum[i]=-1;
        for(int i=1;i<=n;i++)
            sum[i]+=sum[i-1];
        for(int u=1;u<=bn;u++)
        {
            int c=0,mx=0;
            for(int i:vec[u])
            {
                chkmax(ans[u],cnt[u]+cnt[v]-c+sum[n]-sum[i-1]+mx);
                c++,chkmax(mx,c+sum[i]);
            }
            chkmax(ans[u],mx+cnt[v]);
        }
    }
}
void solve_b()
{
    maxcur=0;
    for(int i:vb)chkmax(maxcur,cnt[i]);
    for(int k=1;k<=maxcur;k++)
    {
        pre[0]=-1;
        for(int i=1;i<=n;i++)
            pre[i]=(rk[i]-k<0?-1:vec[a[i]][rk[i]-k]);
        for(int i=2;i<=n;i++)chkmax(pre[i],pre[i-1]);
        for(int u=1;u<=bn;u++)
        {
            int res=0,tot=0;
            for(int i:vec[u])
            {
                if(!~pre[i-1]){res++;continue;}
                while(tot<cnt[u]&&vec[u][tot]<pre[i-1])tot++;
                chkmax(ans[u],k+cnt[u]-res+tot),res++;
            }
            if(~pre[n])
            {
                while(tot<cnt[u]&&vec[u][tot]<pre[n])tot++;
                chkmax(ans[u],k+cnt[u]-res+tot);
            }
        }
    }
}
void solve()
{
    scanf("%lld",&n),B=pow(n,0.5),bn=o=0;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]),b[++bn]=a[i];
    sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
    for(int i=1;i<=bn;i++)
        cnt[i]=ans[i]=0,vec[i].clear();
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+bn,a[i])-b;
    maxn=0,va.clear(),vb.clear();
    for(int i=1;i<=n;i++)
        maxn=max(maxn,++cnt[a[i]]),vec[a[i]].push_back(i),rk[i]=cnt[a[i]];
    for(int i=1;i<=bn;i++)
        cnt[i]>B?va.push_back(i):vb.push_back(i);
    solve_a(),solve_b();
    for(int i=1;i<=bn;i++)chkmax(o,ans[i]);
    printf("%lld\n",o);
    for(int i=1;i<=bn;i++)
        if(ans[i]==o)printf("%lld\n",b[i]);
}
main()
{
    scanf("%lld",&T);
    while(T--)solve();
    return 0;
}

::::