| 部落战争地图 — Supercell、部落冲突 |
这是问题的建设性版本。版本之间的区别在于,在这个版本中,您需要构造一个答案或报告不可能,并且 $$$0 \leq b_i \leq 10^9$$$。只有解决了该问题的所有版本,您才能破解。
建造大师不喜欢重复性任务——修复基地、升级市政厅十五次,以及做更多关于 MEX 的编程问题。所以,这不会是普通的 MEX 问题。
对于任何正整数 $$$k$$$,定义 $$$k$$$-墨西哥 整数集合 $$$S$$$ 的 是 $$$k$$$ 中不存在于 $$$S$$$ 中的第 $$$k$$$ 个最小非负整数。例如,$$$[1, 2, 1]$$$ 的 $$$1$$$-mex 和 $$$2$$$-mex 分别是 $$$0$$$ 和 $$$3$$$。
设 $$$n$$$ 为正整数,并考虑非负整数数组 $$$[a_1, \ldots, a_n]$$$。确定是否存在非负整数数组 $$$[b_1, \ldots, b_n]$$$ 使得:
- 对于所有 $$$1 \leq i \leq n$$$,$$$[b_1, \ldots, b_i]$$$ 的 $$$(n-i+1)$$$-mex 为 $$$a_i$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一行包含“是“或”NO”,表示数组$$$b$$$是否存在。您可以在任何情况下输出答案(上限或下限)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。
然后,如果您回复“是", 打印包含 $$$n$$$ 整数 $$$b_1, \ldots, b_n$$$ ($$$0 \leq b_i \leq 10^9$$$) 的第二行,这样对于所有 $$$1 \leq i \leq n$$$,$$$[b_1, \ldots, b_i]$$$ 是 $$$a_i$$$。
示例
输入复制
633 3 132 1 3101247 5 2 266 6 6 4 3 3
输出复制
YES 2 0 2 NO YES 67 NO NO YES 5 2 1 5 2 0
注意
在第一个测试用例中,数组 $$$a = [3, 3, 1]$$$。我们可以检查数组 $$$b = [2, 0, 2]$$$ 是否满足条件,因为:
- $$$[b_1] = [2]$$$ 的 $$$3$$$-mex 为 $$$a_1 = 3$$$,
- $$$[b_1, b_2] = [2, 0]$$$ 的 $$$2$$$-mex 为 $$$a_2 = 3$$$,
- $$$[b_1, b_2, b_3] = [2, 0, 2]$$$ 的 $$$1$$$-mex 为 $$$a_3 = 1$$$。
在第二个测试用例中,数组 $$$a = [2, 1, 3]$$$。可以看出不存在合适的数组$$$b$$$。
在第三个测试用例中,数组 $$$a = [0]$$$。我们可以检查数组 $$$b = [67]$$$ 是否满足条件,因为 $$$[b_1] = [67]$$$ 的 $$$1$$$-mex 为 $$$a_1 = 0$$$。