E. MEX Count

Codeforces 第 1034 轮 (Div. 3) E

问题描述

每组测试时间限制： 3 秒 每组测试内存限制： 256 MB

定义一个数组的 MEX (最小未出现值) 为数组中未出现的最小非负整数。例如：

• $\text{MEX}([2,2,1]) = 0$ 因为 $0$ 不在数组中。
• $\text{MEX}([3,1,0,1]) = 2$ 因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。
• $\text{MEX}([0,3,1,2]) = 4$ 因为 $0$, $1$, $2$, 和 $3$ 都在数组中，但 $4$ 不在。

给定一个大小为 $n$ 的非负整数数组 $a$。

对于所有的 $k$ ($0 \leq k \leq n$)，计算从 $a$ 中移除恰好 $k$ 个值后，$\text{MEX}(a)$ 可能有多少个不同的值。

输入

第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) — 数组 $a$ 的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq n$)。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一行包含 $n+1$ 个整数 — 对于 $k = 0, 1, \ldots, n$，移除恰好 $k$ 个值后 $\text{MEX}(a)$ 可能的值的数量。

题解

关键洞察

与其考虑从数组中移除元素，不如将其看作是向一个初始为空的数组中添加元素。这个角度使问题变得更加清晰。

理解 MEX 的要求

为了使一个数组的 $\text{MEX} = k$，它必须满足两个条件：

1. 所有从 $0$ 到 $k-1$ 的值必须存在于数组中
2. 值 $k$ 必须不存在于数组中

算法概述

1. 统计可用元素：首先，计算原始数组中每个值出现的次数。

2. 计算所需元素：对于每个可能的 MEX 值 $m$：

   • 我们需要至少一个从 $0$ 到 $m-1$ 的每个值的出现
   • 我们必须避免添加任何值 $m$ 的出现

3. 找到有效范围：对于每个 MEX 值 $m$，确定在保持 $\text{MEX} = m$ 的情况下可以添加的元素范围。

4. 使用差分数组：我们使用差分数组来高效地跟踪哪些位置可以实现每个 MEX 值。

5. 前缀和：最后，计算差分数组的前缀和，以获得每个 MEX 值的最终计数。

时间复杂度

• 时间: $O(n)$
• 空间: $O(n)$

提交链接