← 返回题目列表

Codeforces · 1870/G

G. MEX机制化

中文机器翻译题面 查看原题

让我们定义$$$f(S)$$$。令 $$$S$$$ 为非负整数的多重集(即,它可以包含重复元素)。在一次操作中,您可以选择 $$$S$$$ 的任何非空子集(也可以包含重复元素),从 $$$S$$$ 中删除该子集(其中的所有元素),并将删除的子集的 MEX 添加到 $$$S$$$ 中。您可以执行任意数量的此类操作。完成所有操作后,$$$S$$$ 应恰好包含 $$$1$$$ 数字。 $$$f(S)$$$ 是在任何操作序列之后$$$S$$$ 中可以保留的最大数字。

给定一个非负整数数组 $$$a$$$,长度为 $$$n$$$。对于每个 $$$n$$$ 前缀,如果 $$$S$$$ 是相应的前缀,则计算 $$$f(S)$$$(对于第 $$$i$$$ 个前缀,$$$S$$$ 由数组 $$$a$$$ 的前 $$$i$$$ 元素组成)。

数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如:

- $$$[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 \cdot 10^5$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$。

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

输出

对于每个测试用例,输出 $$$n$$$ 数字:$$$f(S)$$$ 对于数组 $$$a$$$ 的每个 $$$n$$$ 前缀。

示例

输入 #1

4
8
179 57 2 0 2 3 2 3
1
0
3
1 0 3
8
1 0 1 2 4 3 0 2

输出 #1

179 2 3 3 3 4 4 5 
1 
1 2 2 
1 2 2 3 3 5 5 5

注意

考虑第一个测试用例。对于长度为 $$$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\}$$$。这就是答案。