题解 | 小苯的极大支配

目前看到的做法都带一个 $\log{n}$ ，这里给一个严格的线性时间做法。

记数字 $x$ 的出现次数为 $\operatorname{cnt}(x)$ 。

需要删除的元素个数等于数组长度减去可以保留的元素个数，当支配数为 $x$ 时，可以保留的元素个数为 $\operatorname{cnt}(x)+\sum_{i=1}^{x-1}\min(\operatorname{cnt}(i),\operatorname{cnt}(x)-1)$ 。

记：

$f(x)=\sum_{i=1}^x\operatorname{cnt}(i)$
$g(x)$ 为满足 $1\le i\le x$ 且 $\operatorname{cnt}(i)\ge\operatorname{cnt}(x)-1$ 的 $i$ 的个数
$h(x)$ 为满足 $1\le i\le x$ 且 $\operatorname{cnt}(i)\ge\operatorname{cnt}(x)-1$ 的 $\operatorname{cnt}(i)$ 之和

通过分析哪些数被 $\min$ “削平”，计算出可以保留的元素个数为 $f(x)-h(x)+g(x)\cdot(\operatorname{cnt}(x)-1)+1$ ，因此问题归结于如何对每个 $x$ 计算 $f(x),g(x),h(x)$ 。 $f(x)$ 通过前缀和技巧可以在 $O(n)$ 的总时间内计算，而 $g(x),h(x)$ 均具有二维偏序的形式，利用树状数组可以在 $O(n\log{n})$ 的总时间内计算，因此很容易得到一个最坏时间复杂度为 $O(n\log{n})$ 的算法。但通过挖掘更多性质，可以得到一个严格线性的做法。

当 $x<y$ 且 $\operatorname{cnt}(x)\le\operatorname{cnt}(y)$ 时，显然以 $x$ 作为支配数劣于以 $y$ 作为支配数，所以可以通过构建单调栈确定一系列候选支配数，使得它们的值递增而出现次数递减，最优的支配数一定在这些候选支配数中产生。

按照值从小到大、出现次数从多到少的顺序遍历候选支配数，假设上一个考虑的支配数是 $y$ ，当前考虑的支配数是 $x$ 。

作为前缀和， $f(x)$ 的计算是简单的： $f(x)=f(y)+\sum_{z=y+1}^x\operatorname{cnt}(z)$ 。

记集合 $D(x)=\{z\in[1,x]\mid\operatorname{cnt}(x)-1\le\operatorname{cnt}(z)\}$ ，集合 $D(y)=\{z\in[1,y]\mid\operatorname{cnt}(y)-1\le\operatorname{cnt}(z)\}$ ， $\Delta_1=\{z\in[1,y]\mid\operatorname{cnt}(x)-1\le\operatorname{cnt}(z)<\operatorname{cnt}(y)-1\}$ ， $\Delta_2=\{z\in[y+1,x]\mid\operatorname{cnt}(x)-1\le\operatorname{cnt}(z)\}$ ，显然 $D(x)$ 是 $D(y),\Delta_1,\Delta_2$ 三者的不交并。因此 $g(x)=\lvert D(x)\rvert=g(y)+\lvert\Delta_1\rvert+\lvert\Delta_2\rvert$ ， $h(x)=\sum_{z\in D(x)}\operatorname{cnt}(z)=h(y)+\sum_{z\in\Delta_1}\operatorname{cnt}(z)+\sum_{z\in\Delta_2}\operatorname{cnt}(z)$ ，问题归结于如何求出 $\Delta_1,\Delta_2$ 。

为了求出 $\Delta_1$ ，可以将 $\{1,2,\dots,n\}$ 按照出现次数排序（由于出现次数不超过 $n$ ，因此可以用 $O(n)$ 复杂度的计数排序），记出现次数第 $k$ 少的数为 $s(k)$ 。在遍历候选支配数 $x$ 的过程中维护指针 $p(x)$ ，使其指向首个出现次数大于等于 $\operatorname{cnt}(x)-1$ 的数，即 $\operatorname{cnt}(s(p(x)-1))<\operatorname{cnt}(x)-1\le\operatorname{cnt}(s(p(x)))$ ，则 $\Delta_1$ 包含了指针从 $p(y)$ 向左移动到 $p(x)$ 新扫过的位于 $[1,y]$ 之间的数，即 $\Delta_1=\{s(k)\mid k\in[p(x),p(y)-1]\}\cap[1,y]$ 。

$\Delta_2$ 按照定义直接求解即可。

最坏时间复杂度 $O(n)$ ，提交链接，核心代码片段如下

int main() {
  int t = read();
  while (t--) {
    int n = read();
    vector<int> cnt(n);
    for (int i = 0; i < n; i++) cnt[read() - 1]++;
    vector<int> s(n);
    ranges::iota(s, 0);
    counting_sort(s, n, [&cnt](int x) { return cnt[x]; });
    vector<int> stk;
    for (int x = 0; x < n; x++) {
      while (!stk.empty() && cnt[stk.back()] <= cnt[x]) stk.pop_back();
      stk.push_back(x);
    }
    int f = 0, g = 0, h = 0;
    int mx = 0;
    int p = n;
    for (int idx = 0; idx < stk.size(); idx++) {
      int x = stk[idx], y = idx == 0 ? -1 : stk[idx - 1];
      while (p - 1 >= 0 && cnt[s[p - 1]] >= cnt[x] - 1) {
        p--;
        if (s[p] <= y) {
          g++;
          h += cnt[s[p]];
        }
      }
      for (int z = y + 1; z <= x; z++) {
        f += cnt[z];
        if (cnt[z] >= cnt[x] - 1) {
          g++;
          h += cnt[z];
        }
      }
      mx = max(mx, f - h + g * (cnt[x] - 1) + 1);
    }
    cout << n - mx << '\n';
  }
  return 0;
}