CF1930C Lexicographically Largest

Stack 有一个长度为 $n$ 的数组 $a$，以及一个空集合 $S$。注意，$S$ 不是多重集合。 他将恰好进行 $n$ 次如下三步操作： 1. 选择一个下标 $i$，满足 $1 \leq i \leq |a|$。 2. 将 $a_i + i$ 插入 $S$。 3. 从 $a$ 中删除 $a_i$。注意，$a_i$ 右侧所有元素的下标都会减 $1$。 注意，经过 $n$ 次操作后，$a$ 会变为空。 Stack 现在将构造一个新数组 $b$，它是将 $S$ 按降序排列后的结果。形式化地说，$b$ 是一个大小为 $|S|$ 的数组，其中 $b_i$ 表示 $S$ 中第 $i$ 大的元素，$1 \leq i \leq |S|$。 请你求出 Stack 能够构造出的字典序最大的 $b$。 $^\dagger$ 集合只能包含唯一元素。向集合中插入已存在的元素不会改变集合中的元素。 $^\ddagger$ 如果满足以下任一条件，则数组 $p$ 的字典序大于序列 $q$： - $q$ 是 $p$ 的前缀，且 $p \ne q$； - 在 $p$ 和 $q$ 第一个不同的位置，$p$ 的该元素大于 $q$ 的对应元素。 例如，$[3,1,4,1,5]$ 的字典序大于 $[3,1,3]$、$[\,]$ 和 $[3,1,4,1]$，但小于 $[3,1,4,1,5,9]$、$[3,1,4,1,5]$ 和 $[4]$。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$），表示数组 $a$ 的长度。 每组测试数据的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_{n}$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。 所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每组测试数据，输出字典序最大的 $b$。

在第一个测试用例中，第一次操作选择 $i=1$，将 $a_1 + 1 = 3$ 插入 $S$，并从 $a$ 中删除 $a_1$。第一次操作后，$a=[1]$。第二次操作再次选择 $i=1$，将 $a_1 + 1 = 2$ 插入 $S$。因此 $S=\{2, 3\}$，$b = [3, 2]$。 注意，如果第一次操作选择 $i=2$，第二次操作选择 $i=1$，则 $S=\{3\}$，因为 $3$ 会被插入两次，最终 $b=[3]$。 由于 $[3,2]$ 的字典序大于 $[3]$，所以应该在第一次操作时选择 $i=1$。 在第二个测试用例中，每次操作都选择最后一个元素。 由 ChatGPT 4.1 翻译