P8330 [ZJOI2022] 众数 题解

Description

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，问选一段区间，它的价值是里面的众数个数 $+$ 外面的众数个数，求最大价值，以及所有满足这个最大价值的区间的外面的众数颜色。

$\sum n\leq 5\times 10^5,n\leq 2\times 10^5$。

Solution

考虑根号分治。

定义一个大的颜色指出现次数 $>\sqrt n$ 的颜色，小的颜色指出现次数 $\leq\sqrt n$ 的颜色。

首先考虑两个众数中至少一个是大颜色的贡献。

假设大颜色为 $x$，另一个为 $y$。

第一种情况是形如 $\texttt{xxxxyyyyyxxxx}$ 即 $x$ 在两边，$y$ 在中间的贡献。这时会发现一个区间 $[l,r]$ 的答案就是 $x$ 的出现次数 $+$ $[l,r]$ 中 $y$ 的出现次数 $-$ $[l,r]$ 中 $x$ 的出现次数，这个东西很容易搞成区间和的形式，搞个最大子段和即可做到单次 $O(n)$。

容易发现最优情况一定满足选定区间的左右端点都是 $y$，所以只要对于所有颜色为 $y$ 的位置计算答案即可做到单次 $O(cnt_y)$。

对于 $\texttt{yyyyxxxxxyyyy}$ 的情况是同理的，所以这一部分的总时间复杂度为 $O(\sqrt n)$。

---

然后考虑 小-小 的情况。

这里先枚举区间外的众数 $x$，容易发现最优情况的区间 $[l,r]$ 一定满足：$l=1$ 或 $a_{l-1}=x$，和 $r=n$ 或 $a_{r+1}=x$。

这时只要枚举这些 $[l,r]$ 再求出 $[l,r]$ 之间的众数即可得出答案。

但是这样要求 $O(n\sqrt n)$ 次区间众数，显然过不了。

观察到这里只需要考虑 $[l,r]$ 中出现次数 $\leq \sqrt n$ 的数的众数，所以 $[l,r]$ 的答案也 $\leq \sqrt n$。

于是可以依次枚举 $r$，维护 $s_l$ 表示 $[l,r]$ 的众数。然后对于所有 $r$ 前且颜色和 $r$ 相等的位置 $i$，需要对于所有 $j\leq i$ 的 $s_j$ 对 $[i,r]$ 中 $a_i$ 的个数取 $\max$。

注意到这里 $s$ 一定是单调不增的，所以只需从后往前扫，如果能更新就更新，否则就退出。

然后右端点为 $r+1$ 的答案即为 $\max{c_i+cnt_{[1,i-1],a_{r+1}}+cnt_{[r+1,n],a_{r+1}}}$，这个暴力枚举颜色与 $r+1$ 相同的 $i$ 即可。

容易发现一次更新至少会使 $s$ 的总和 $+1$，而最终 $s_i\leq \sqrt n$，所以时间复杂度就是 $O(n\sqrt n)$。

总的时间复杂度：$O(n\sqrt n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 2e5 + 5;

int n, m, b;
int a[kMaxN], unq[kMaxN], pos[kMaxN], res[kMaxN], sum[kMaxN];
std::vector<int> v[kMaxN];

void discrete() {
  b = sqrt(n);
  for (int i = 1; i <= n; ++i)
    unq[i] = a[i];
  std::sort(unq + 1, unq + 1 + n);
  m = std::unique(unq + 1, unq + 1 + n) - (unq + 1);
  for (int i = 1; i <= n; ++i)
    v[i].clear(), res[i] = 0;
  for (int i = 1; i <= n; ++i) {
    a[i] = std::lower_bound(unq + 1, unq + 1 + m, a[i]) - unq;
    pos[i] = v[a[i]].size();
    v[a[i]].emplace_back(i);
  }
}

int big1(int x, int y) { // xxxxxyyyyyyyyyxxxxx
  static int pre1[kMaxN], pre2[kMaxN];
  int mi = 1e9, ret = 0;
  for (int i = 0; i < (int)v[y].size(); ++i) {
    pre1[i] = sum[v[y][i]] + i + 1;
    pre2[i] = sum[v[y][i] - 1] + i;
    mi = std::min(mi, pre2[i]);
    ret = std::max(ret, pre1[i] - mi);
  }
  return ret + v[x].size();
}

int big2(int x, int y) { // yyyyyxxxxxxyyyyyy
  static int pre[kMaxN], suf[kMaxN], mx[kMaxN];
  for (int i = 0; i < (int)v[y].size(); ++i) {
    pre[i] = sum[v[y][i]] + i + 1;
    suf[i] = sum[n] - sum[v[y][i] - 1] + v[y].size() - i;
    mx[i] = (i == 0 ? pre[i] : std::max(mx[i - 1], pre[i]));
  }
  int now = -1e9, ret = mx[(int)v[y].size() - 1];
  for (int i = (int)v[y].size() - 1; i; --i) {
    now = std::max(now, suf[i]);
    ret = std::max(ret, now + pre[i - 1]);
  }
  ret = std::max(ret, now);
  return ret + v[x].size();
}

void solve_big() {
  for (int x = 1; x <= m; ++x) {
    if (v[x].size() <= b) continue;
    for (int i = 1; i <= n; ++i)
      sum[i] = sum[i - 1] - (a[i] == x);
    for (int y = 1; y <= m; ++y) {
      res[x] = std::max(res[x], big1(x, y));
      res[y] = std::max(res[y], big2(x, y));
    }
  }
}

void solve_small() {
  static int c[kMaxN], cnt[kMaxN];
  // c[i] : [i, r] 的众数
  std::fill_n(c + 1, n, 0);
  std::fill_n(cnt + 1, n, 0);
  for (int i = 1; i <= n; ++i) {
    if (v[a[i]].size() > b) continue;
    res[a[i]] = std::max(res[a[i]], c[1] + (int)v[a[i]].size() - pos[i]);
    for (int j = pos[i] - 1; ~j; --j) {
      res[a[i]] = std::max(res[a[i]], c[v[a[i]][j] + 1] + (int)v[a[i]].size() - pos[i] + j + 1);
    }
    for (int j = pos[i]; ~j; --j) {
      for (int k = v[a[i]][j]; k && c[k] <= pos[i] - j + 1; --k)
        c[k] = pos[i] - j + 1;
    }
  }
  int mx = 0;
  for (int i = n; i; --i) {
    res[a[i]] = std::max(res[a[i]], mx + pos[i] + 1);
    mx = std::max(mx, ++cnt[a[i]]);
  }
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i)
    std::cin >> a[i];
  discrete(), solve_big(), solve_small();
  int mx = 0;
  for (int i = 1; i <= m; ++i) mx = std::max(mx, res[i]);
  std::cout << mx << '\n';
  for (int i = 1; i <= m; ++i)
    if (res[i] == mx)
      std::cout << unq[i] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}