CF1446D2 Frequency Problem (Hard Version)

· · 题解

E. CF1446D2 Frequency Problem (Hard Version)

关键结论：原序列众数 M 为答案序列众数之一，若非，可不断扩张直到 M 成为区间众数之一，此时因存在其它区间众数，故合法。

根据结论，考虑枚举所有其他数 v，求出所有使得 M, v 出现次数相同的子区间 [l, r]，如果存在出现次数比 M 出现次数更大的数，则 [l, r] 不优于答案，不会产生贡献。

求 l, r 为经典套路：将 M 视为 +1，v 视为 -1，其它数视为 0，则和为 0 的区间合法。据此有 \mathcal{O}(occ(M) + occ(v)) 求出 M, v 答案的做法：初始化 val_0 = acc = 0，其它位置 val_i = +\infty。按顺序考虑所有 M 或 v 的出现位置 p_1, p_2, \cdots, p_k：

第二和第三步简称用 (acc, p_i, p_{i + 1} - 1) 三元组更新答案。

考虑 SDOI2022 D1T1 的技巧，将前缀和序列用折线描述，发现仅 \mathcal{O}(occ(v)) 个位置有用。下图中，实线部分可能对答案产生贡献。

考虑 v 相邻的两次出现 pre 与 cur，分别是第 p 和 p + 1 次。令 pre 之前 M 出现了 pos 次，pre 与 cur 之间 M 出现了 num 次。容易发现 pre 处的折线高度为 acc = pos - p。

令折线在 pre 之前的历史最大值为 hmax，在 cur 之后的历史最小值为 hmin，则对于 pre 和 cur 之间的上升线段而言，仅有高度 \leq hmax 与 \geq hmin 的部分有用。

令 skip = \max(0, hmin - 1 - acc)，则 skip 表示当前长为 num 的线段在 skip + 1 \sim num 处有用，即上图 y\sim cur 的部分。

可使用小技巧避免记录 hmax：从 1 到 skip 枚举 i，若 val_{acc +i} = +\infty 说明 acc + i 已经超出 hmax 范围，否则用 (acc + i, P(M, pos + i), \min(P(M, pos + i + 1), cur) - 1) 更新答案，其中 P(i, j) 表示 i 第 j 次出现在序列中的位置，若 j 大于 occ(i) 则视 P(i, j) = n + 1。

同样的，从 skip + 1 到 num 枚举 i，用上式更新答案。

最后不要忘了用 (acc + num - 1, cur, \min(P(M, pos + num + 1), P(v, p + 2)) - 1) 更新答案。暂时性地令 a_0 = a_{n + 1} = v 可以在一开始和最后对边界进行讨论，但当 p = occ(v) 即 cur = n + 1 时不能进行前一句话所描述的答案更新。

时间复杂度 \mathcal{O}(\sum occ(v))，即 \mathcal{O}(n)，比根号分治优秀不少。在洛谷上获得了最优解（2022.7.10）。

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 2e5 + 5;
int n, a[N], occ[N], val[N << 1], ans;
vector<int> buc[N];
int P(int v, int p) {return p == buc[v].size() ? n + 1 : buc[v][p];}
bool Med;
int main() {
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  memset(val, 0x3f, sizeof(val)), val[N] = 0;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i], buc[a[i]].push_back(i);
  int mx = 0, oc = 0, id;
  for(int i = 1; i <= n; i++)
    if(buc[i].size() > mx) mx = buc[i].size(), oc = 1, id = i;
    else oc += buc[i].size() == mx;
  if(oc >= 2) cout << n << endl, exit(0);
  for(int it : buc[id]) occ[it] = 1;
  for(int i = 1; i <= n + 1; i++) occ[i] += occ[i - 1];
  for(int i = 1; i <= n; i++) {
    if(i == id) continue;
    if(buc[i].empty()) continue;
    static int w[N], suf[N], modi[N];
    int cnt = 0;
    for(int p = 0; p < buc[i].size(); p++) w[p] = occ[buc[i][p]] - p - 1;
    suf[buc[i].size()] = w[buc[i].size()] = buc[id].size() - buc[i].size();
    for(int p = buc[i].size() - 1; ~p; p--) suf[p] = min(w[p], suf[p + 1]);
    auto upd = [&](int v, int p, int q) {
      if(val[N + v] > N) modi[++cnt] = N + v, val[N + v] = p;
      ans = max(ans, q - val[N + v]);
    };
    for(int p = 0; p <= buc[i].size(); p++) {
      int pre = p ? buc[i][p - 1] : 0, cur = p < buc[i].size() ? buc[i][p] : n + 1;
      int pos = occ[pre], num = occ[cur] - occ[pre], acc = p ? w[p - 1] : 0;
      int skip = max(0, suf[p] - acc - 1);
      for(int q = 1; q <= skip; q++) {
        if(val[N + acc + q] > N) break;
        upd(acc + q, buc[id][pos + q - 1], min(cur, P(id, pos + q)) - 1);
      }
      for(int q = skip + 1; q <= num; q++) upd(acc + q, buc[id][pos + q - 1], min(cur, P(id, pos + q)) - 1);
      if(p < buc[i].size()) upd(acc + num - 1, cur, min(P(id, pos + num), P(i, p + 1)) - 1);
    }
    for(int p = 1; p <= cnt; p++) val[modi[p]] = 1e9;
  }
  cout << ans << endl;
  return cerr << "Time: " << clock() << "\n", 0;
}
/*
2022/7/10
start coding at
finish debugging at
*/