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;
}