mydcwfy's Blog

ZJOI2022 众数

Posted on
Symbols count in article: 3.3k Reading time ≈ 7 mins.

非常厉害的 分块 / 平衡规划 题目，不卡常，码量小，比较有趣。

题目传送门 LOJ

题意：给定序列 $a$，可以任选一个区间加一个数，问最后众数个数的最大值和可能的众数。$n\leq 2\times 10 ^ 5, \sum n\leq 5\times 10 ^ 5$，3s。

首先相当于是选一个区间使得内外众数个数和最大。

设 $\text{occ}(i)$ 表示 $i$ 出现的次数，我们就是要利用好 $\sum \text{occ}(i) = n$ 的性质。

首先，如果我们确定的内部或者是外部的颜色，我们可以在线性时间内求出最大答案。具体的，比如我们已经确定的外部的颜色，我们再枚举内部颜色。容易发现我们一定两边都是这个颜色时最优，否则我们可以缩短使得刚好两边都是这个颜色。容易发现可以转化成前缀和，我们用前缀最大值更新当前右端点的答案，可以做到 $\text{occ}(i)$，所以确定了一个颜色后，可以在 $O(n)$ 时间得到。

但是不能每个颜色都扫一边，我们可以考虑平衡规划，将 $\text{occ}(i) > B$ 的颜色用这个方法做，前面的复杂度为 $O(\dfrac {n ^ 2}B)$。剩下的都是 $\text{occ}(i)\leq B$ 的颜色了。

我们还是得枚举外部颜色，容易发现现在内部的众数答案一定 $\leq B$，我们可以考虑确定左端点时，暴力将 $ans\in [1, B]$ 时满足条件的最小的右端点全部统计一遍，这样就可以做到 $O(\text{occ}(i)B)$ 的复杂度。

将所有的全部扫一遍，于是总复杂度 $O(nB)$，与上一个平衡规划一下，复杂度就是 $O(n\sqrt n)$，不算卡常。

注意有一些实现细节，比如可能外部颜色只出现在左边，右边没有可能导致统计漏。可以自己手搓一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
void solvebig(int col)
{
    for (int i = 1; i <= n; ++ i)
        cnt[i] = cnt[i - 1] + (a[i] == col);
    int tres = 0;
    for (int i = 1; i <= sz; ++ i) {
        int ed = app[i].size();
        for (int j = 0; j < ed; ++ j)
            pre[j] = cnt[app[i][j] - 1] - j + 1, suf[j] = cnt[n] - cnt[app[i][j]] + j;
        for (int j = 1; j < ed; ++ j) chkmax(pre[j], pre[j - 1]);
        for (int j = ed - 2; ~j; -- j) chkmax(suf[j], suf[j + 1]);
        for (int j = 0; j < ed; ++ j) chkmax(tres, pre[j] + suf[j]);
    }
    // printf("Big Col %d %d\n", col, tres);
    if (chkmax(res, tres)) ans.clear();
    if (res == tres) ans.push_back(col);
    for (int i = 1; i <= sz; ++ i) {
        int ed = app[i].size(), tres = 0;
        for (int j = 0; j < ed; ++ j)
            pre[j] = j - cnt[app[i][j]] + 1, suf[j] = cnt[app[i][j] - 1] + ed - j;
        chkmax(pre[0], 0), chkmax(suf[ed - 1], cnt[n]);
        for (int j = 1; j < ed; ++ j) chkmax(pre[j], pre[j - 1]);
        for (int j = ed - 2; ~j; -- j) chkmax(suf[j], suf[j + 1]);
        for (int j = 0; j < ed - 1; ++ j) chkmax(tres, pre[j] + suf[j + 1]);
        // printf("Col2 %d %d %d\n", i, col, tres);
        if (chkmax(res, tres)) ans.clear();
        if (res == tres) ans.push_back(i);
    }
}

void solvesmall(int col)
{
    auto &ap = app[col];
    app[col].insert(app[col].begin(), 0);
    int ed = ap.size(), tres = 0;
    for (int j = 0, cur; j < ed; ++ j) {
        cur = j;
        for (int del = 1; del <= lim; ++ del) {
            if (mx[ap[j] + 1][del] > n + 1) break;
            while (cur < ed && ap[cur] <= mx[ap[j] + 1][del]) cur ++;
            chkmax(tres, ed - cur + j + del);
        }
    }
    app[col].erase(app[col].begin());
    // printf("Res : %d %d\n", col, tres);
    if (chkmax(res, tres)) ans.clear();
    if (res == tres) ans.push_back(col);
}

void work()
{
    std::cin >> n;
    lim = std::max(std::sqrt(n) + 1, 1.), res = 0;
    for (int i = 1; i <= n; ++ i) app[i].clear();
    for (int i = 1; i <= n; ++ i)
        scanf("%d", a + i);
    std::vector<int> ws(n);
    for (int i = 0; i < n; ++ i) ws[i] = a[i + 1];
    std::sort(ws.begin(), ws.end());
    ws.erase(std::unique(ws.begin(), ws.end()), ws.end());
    sz = ws.size();
    for (int i = 1; i <= n; ++ i)
        a[i] = std::lower_bound(ws.begin(), ws.end(), a[i]) - ws.begin() + 1;
    std::cerr << a[n - 6] << std::endl;
    for (int i = 1; i <= n; ++ i) app[a[i]].push_back(i);
    for (int i = 1; i <= n + 1; ++ i)
        for (int j = 1; j <= lim; ++ j) mx[i][j] = INF;
    for (int i = 1; i <= sz; ++ i) {
        if ((int) app[i].size() > lim) continue;
        int ed = app[i].size();
        for (int j = 0; j < ed; ++ j)
            for (int del = 1; del <= lim && j + del <= ed; ++ del)
                chkmin(mx[app[i][j]][del], app[i][j + del - 1]);
    }
    for (int i = n - 1; i; -- i)
        for (int j = 1; j <= lim; ++ j) chkmin(mx[i][j], mx[i + 1][j]);
    for (int i = 1; i <= sz; ++ i)
        if ((int) app[i].size() > lim) solvebig(i);
        else solvesmall(i);
    printf("%d\n", res);
    std::sort(ans.begin(), ans.end());
    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
    for (int x : ans) printf("%d\n", ws[x - 1]);
}