题解：P8330 [ZJOI2022] 众数

· · 题解

根号分治大成题。蒟蒻不看题解想了一天。

题目意思就是在序列中删掉一区间，分别取剩下的段和删掉的段中的众数的个数，问他们的和最大能为多少，还有能取到最大和的剩下那段众数的方案。

直接做是不行的，用根号分治的方法创造条件。

1. 处理小于 \sqrt{n} 个数字。

这种情况容易想到对每个数字分开处理，花费 O(n) 的时间。

设处理到的数字是 i。可以想到对于该数在区间内的情况，若外面选的数字是 j，我们把数组中 i 看作 +1，j 看作 -1，发现答案就是一段区间的和加上数组中 j 的个数。做前缀和，需要查询历史最小值，发现可以维护。

对于该数在区间外面的情况，可设 f_j 表示当前区间内选 j 最大取到多少个数，发现也可以维护。

这样我们可以处理较大的 \sqrt{n} 个数，剩下的数就出现次数只小于等于 \sqrt{n}。

2. 每个数字出现次数小于等于 \sqrt{n}。

发现区间内和区间外的众数个数均小于等于 \sqrt{n} ，对每个点去求若作为左端点，那么右端点至少是几，区间内众数为 s。然后显然可以用双指针求解。

因为众数个数随区间长度增加单调递增，所以可以从后往前求解，设当前点为 i，那么用大于 i 的点 j ，且 a_i=a_j 的点更新即可。

时间复杂度 O(n \sqrt{n} )。我的写法细节巨多。

#include <bits/stdc++.h>
using namespace std;

int TAT;
int n, parter, a[500002], nn, aa[500002], cnt[500002];
int Ans, haveAns[500002];
void update(int s,int num){
    if(s > Ans) Ans = s, haveAns[num] = Ans;
    else if(s == Ans) haveAns[num] = Ans;
}

int adder, have[500002], Max[500002];
int f[500002];
void solve1(){
    for(int i=1;i<=nn;i++){
        if(cnt[i] <= parter) continue;

        // 把i看成1，把a[j]看成-1，前缀和have[a[j]]
        // 全局加1   单点-1   查询单点历史最小值 
        for(int j=1;j<=nn;j++) have[j] = 0, Max[j] = 0;
        adder = 0;
        for(int j=1;j<=n-1;j++){
            if(a[j] == i) adder++;
            have[a[j]]--, Max[a[j]] = max(Max[a[j]], -have[a[j]]-adder);
            update(cnt[a[j+1]]+have[a[j+1]]+adder+Max[a[j+1]], a[j+1]);
        }// 在内

        adder = 0;
        for(int j=1;j<=nn;j++) f[j] = 0;
        for(int j=1;j<=n;j++){
            if(a[j] == i) adder++;
            f[a[j]] = max(f[a[j]] + 1, adder + 1);
            update(f[a[j]] + cnt[i] - adder, i);
        }// 在外 
    }
}

int head[500002], nxt[500002], zhong[500002];
void solve2(){
    for(int i=1;i<=nn;i++) head[i] = n+1;
    nxt[n+1] = 0;
    for(int i=1;i<=n;i++) zhong[i] = n+1;
    for(int i=n;i>=1;i--){
        if(cnt[a[i]] <= parter) {
            nxt[i] = head[a[i]], head[a[i]] = i;
        }
    }
    for(int i=n;i>=1;i--){
        if(cnt[a[i]] > parter) continue;

        int cnt2 = 0;
        for(int pos1=nxt[i],cnt1=0;pos1;pos1=nxt[pos1],cnt1--){
            while(cnt2 + 1 <= parter && zhong[cnt2+1] < pos1) cnt2++;
            update(cnt[a[i]]+cnt1+cnt2,a[i]);
        }

        for(int j=i,k=1;j!=n+1;j=nxt[j],k++){
            zhong[k] = min(zhong[k], j);
        }
    }
}

int main(){
    //freopen("mode_ex2.in","r",stdin);
    //freopen("zzz.out","w",stdout);

    scanf("%d",&TAT);

    while(TAT--){
        Ans = 0;
        for(int i=1;i<=n;i++) haveAns[i] = 0;

        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]), aa[i] = a[i];
        sort(aa+1,aa+n+1), nn = unique(aa+1,aa+n+1)-aa-1;
        for(int i=1;i<=nn;i++) cnt[i] = 0;
        for(int i=1;i<=n;i++) a[i] = lower_bound(aa+1,aa+nn+1,a[i])-aa, cnt[a[i]]++;

        parter = sqrt(n);
        solve1();
        reverse(a+1,a+n+1);
        solve1();

        solve2();
        reverse(a+1,a+n+1);
        solve2();

        printf("%d\n",Ans);
        for(int i=1;i<=nn;i++) {
            if(haveAns[i] == Ans) printf("%d\n",aa[i]);
        }
    }

    return 0;
}

/*
1
6
2 4 2 4 8 8

8 8 4 2 4 2
*/