P8330 [ZJOI2022] 众数

· · 题解

P8330 [ZJOI2022] 众数

转化一下题意，求出将循环序列切成两段，每段区间众数出现次数之和的最大值。

一般 “出现次数” 都与 根号分治 挂钩，因为出现次数少的数可以直接考虑出现次数，出现次数多的数可以直接考虑每个数，这样就出现了根号。

将出现次数 \geq B 的数成为大数，反之成为小数。

考虑大数在外侧的情况。枚举每个大数 x，先把所有 x 选上，再考虑枚举内层的数 y，那么一段区间 [l, r] 的贡献就是 [l, r] 内 y 的个数减去 x 的个数。这是一个最大子段和问题。区间右端点必然可以调整至仅在 y 出现的位置取到。

大数在内侧同理，只要先把所有 y 选上，贡献取相反数即可。同理，此时区间右端点在 y 出现的前一个位置取到。预处理 [a_i = x] 的前缀和，这样对每个 x 枚举所有 y 的总复杂度就是线性，这部分是 \dfrac {n ^ 2} B。

接下来我们只关心小数配对小数的情况。如果确定了某个小数 x 在外侧，那么容易证明内侧区间 [l, r] 可以调整至满足 l = 1 或 a_{l - 1} = x，且 r = n 或 a_{r + 1} = x。这样一来，可能的内侧区间个数只有出现次数平方个。

这样我们只需求出区间 [l, r] 的众数出现次数（甚至不需要具体值，因为最终内侧会变成外侧，也就是外侧的值才有用）。

普通地求 q 次众数的时间复杂度是莫队或者分块的 q\sqrt n，放在本题肯定不行。

实际上还有一个性质没有用到，就是只需要众数出现次数 \leq B。我们对每个位置 i 预处理出来使得 [i, r] 的众数出现次数等于 j 最小的 r（注意循环序列），记作 p_{i, j}。这个枚举出现次数然后 two-pointers。

这样查询区间 [l, r] 的众数的时候只需要二分出现次数并判断是否有 p_{l, mid} \leq r 即可在对数时间内求众数。可以通过 50pts。

更进一步地，考虑左端点 l 固定，右端点右移的过程，[l, r] 众数的出现次数一定不断增加。根据单调性用指针维护即可。对于每个左端点最多右移 B 次右端点，而指针的移动次数均摊也是 B 次，所以这部分时间复杂度 \mathcal{O}(nB)。

取 B = \sqrt n 得到时空复杂度 \mathcal{O}(n\sqrt n)。注意大小为根号的那一维要放在前面，防止过多 cache miss（卡车丢失，大雾）导致 TLE。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char s = getchar();
    while(!isdigit(s)) s = getchar();
    while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
    return x;
}
const int B = 200;
const int N = 2e5 + 5;
int n, a[N], d[N], ans[N], pointer[B][N];
vector <int> pos[N];
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) pos[i].clear(), ans[i] = 0;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), d[i] = a[i];
    sort(d + 1, d + n + 1);
    for(int i = 1; i <= n; i++) pos[a[i] = lower_bound(d + 1, d + n + 1, a[i]) - d].push_back(i);
    for(int i = 1; i <= n; i++) {
        if(pos[i].size() < B) continue;
        static int pre[N];
        memset(pre, 0, sizeof(pre));
        for(int it : pos[i]) pre[it] = 1;
        for(int p = 1; p <= n; p++) pre[p] += pre[p - 1];
        for(int j = 1; j <= n; j++) {
            if(i == j) continue;
            int mx = 1, cur = 1;
            for(int ind = 1; ind < pos[j].size(); ind++) mx = max(mx, cur = max(1, cur - (pre[pos[j][ind]] - pre[pos[j][ind - 1]]) + 1));
            ans[i] = max(ans[i], mx + (int) pos[i].size());
            mx = cur = 0;
            for(int ind = 1; ind < pos[j].size(); ind++) {
                mx = max(mx, cur += pre[pos[j][ind]] - pre[pos[j][ind - 1]]);
                cur = max(0, cur - 1);
            }
            ans[j] = max(ans[j], mx + (int) pos[j].size());
        }
    }
    int limit = 0;
    for(int i = 1; i <= n; i++) limit = max(limit, (int) pos[i].size());
    limit = min(limit, B - 1);
    for(int i = 1; i <= limit; i++) {
        static int buc[N], mode;
        memset(buc, mode = 0, sizeof(buc));
        for(int l = 1, r = 0; l <= n; buc[a[l++]]--) {
            while(buc[mode] < i) {
                buc[a[r = r < n ? r + 1 : 1]]++;
                if(buc[a[r]] > buc[mode]) mode = a[r];
            }
            pointer[i][l] = r;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(pos[i].size() > limit) continue;
        for(int j = 0; j < pos[i].size(); j++) { // 枚举左端点 l.
            for(int k = 1; k <= limit; k++) if(pointer[k][1] < pos[i][j]) ans[i] = max(ans[i], (int) pos[i].size() - j + k); // 先处理一下 l = 1 的情况.
            int pt = j, p = pos[i][j] + 1;
            if(p > n) continue;
            for(int k = 1; k <= limit; k++) { // 这里不同于题解的是, 我从小到大枚举出现次数, 用指针维护最小的合法右端点, 本质没有太大差别.
                if(pointer[k][p] < p) break; // 如果要绕过去变成外侧就不行了.
                while(pt < pos[i].size() && pos[i][pt] <= pointer[k][p]) pt++; // 出现次数增大使得右端点右移.
                ans[i] = max(ans[i], j + k + 1 + (int) pos[i].size() - pt);
            }
        }
    }
    int mx = 0;
    for(int i = 1; i <= n; i++) mx = max(mx, ans[i]);
    cout << mx << endl;
    for(int i = 1; i <= n; i++) if(ans[i] == mx) printf("%d\n", d[i]);
}
int main() {
    int T;
    cin >> T;
    while(T--) solve();
    return cerr << clock() << endl, 0;
}
/*
2022/5/8
start thinking at ??:??
高妙根号分治题.
先处理大块与大块和小块.
再处理小块之间的情况.
写一个 sqrt log 试试看.
又 T 又 WA, 我不理解.
start coding at 14:42
交换 N, B 两维跑得飞快啊.
实际上将 B 开小一点效率会比较高, 因为对于小数的处理用了巨大的二维数组, 实在是太慢了.
finish debugging at 16:21
*/