CF1870G MEXanization

我们定义 $f(S)$。设 $S$ 是一个非负整数的多重集（即可以包含重复元素）。每次操作，你可以选择 $S$ 的任意非空子集（也可以包含重复元素），将该子集中的所有元素从 $S$ 中移除，并将该子集的 MEX 加入 $S$。你可以进行任意次这样的操作。所有操作结束后，$S$ 中应只剩下恰好一个数。$f(S)$ 表示通过任意操作序列后，$S$ 最终可能剩下的最大数。 给定一个长度为 $n$ 的非负整数数组 $a$。对于它的每个前缀，计算 $f(S)$，其中 $S$ 是对应的前缀（对于第 $i$ 个前缀，$S$ 包含数组 $a$ 的前 $i$ 个元素）。 MEX（minimum excluded）指的是一个数组中未出现的最小非负整数。例如： - $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在数组中。 - $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。 - $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都在数组中，但 $4$ 不在。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）——数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 2 \times 10^5$）——数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $n$ 个数：对于数组 $a$ 的每个前缀，输出对应 $S$ 的 $f(S)$。

考虑第一个测试用例。对于长度为 $1$ 的前缀，初始多重集为 $\{179\}$。如果什么都不做，结果就是 $179$。 对于长度为 $2$ 的前缀，初始多重集为 $\{57, 179\}$。可以通过如下操作序列得到 $2$： 1. 对 $\{57\}$ 进行操作，多重集变为 $\{0, 179\}$。 2. 对 $\{179\}$ 进行操作，多重集变为 $\{0, 0\}$。 3. 对 $\{0\}$ 进行操作，多重集变为 $\{0, 1\}$。 4. 对 $\{0, 1\}$ 进行操作，多重集变为 $\{2\}$。这就是答案。 考虑第二个测试用例。对于长度为 $1$ 的前缀，初始多重集为 $\{0\}$。如果对 $\{0\}$ 进行操作，多重集变为 $\{1\}$。这就是答案。 由 ChatGPT 4.1 翻译