P13610 [NWRRC 2022] Mex and Cards

· · 题解

来点 \operatorname{mex} 节奏

已知 i \in [1,n - 1]，i 数字的出现次数为 a_i，又因为可以通过分成若干组来构造最大值，有一个优美的性质：

ans = \sum_{i = 0}^{n - 1} \min_{ 0 \le j \le i} a_j

我们考虑一个 \operatorname{mex}，它其实是一个逐渐往上堆的过程，我们让它每堆高一层，就加上对应的贡献，那我当我们扫到 a_i，实际上前缀最小值就是我们在这里能多堆高的个数。

有了这个性质之后，我们考虑加入或删除一个数字 v 对前缀最小值数组 b_i 的影响。

我们要找到已 a_v 作为前缀最小值的区间，如果 v 前面有数的出现次数比 a_v 小，那肯定不会产生影响，否则，我们找从 p 开始，第一个小于 v 的位置，计算贡献，直接线段树二分或者二分 + 线段树都可以。

最后时间复杂度是 \mathcal O((n + q)\log{n}) 的。