考虑 $$$p$$$ 的排列 $$$1, 2, \ldots, n$$$。令 $$$s_i$$$ 表示整个前缀 $$$p_1, p_2, \ldots, p_i$$$ 中的反转数量,定义为:
$$s_i = \sum_{1 \le x \lt y \le i} [p_x \gt p_y],$$
其中方括号表示艾弗森括号符号。
对于每个位置 $$$i$$$ ($$$1 \le i \le n$$$),您将获得一个 $$$p_i = x$$$ 或 $$$s_i = x$$$ 形式的条件。你的任务是重建原始排列$$$p$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
对于每个测试用例:第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$)。以下 $$$n$$$ 行中的每一行都包含一个字符 $$$c$$$ ($$$c \in \{\text{'p'}, \text{'s'}\}$$$) 和一个整数 $$$x$$$:
- 如果$$$c = \text{'p'}$$$,则表示$$$p_i = x$$$,其中$$$1 \le x \le n$$$。
- 如果$$$c = \text{'}$$$,则表示$$$s_i = x$$$,其中$$$0 \le x \le \frac{i(i-1)}{2}$$$。
所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
保证有效的排列始终存在。
输出
对于每个测试用例,输出表示排列 $$$p$$$ 的 $$$n$$$ 整数。
如果有多个有效排列,则可以输出其中任何一个。
示例
输入复制
53p 1p 2p 33s 0s 1s 23p 1s 0p 25p 1p 4s 0p 2s 46s 0s 1s 3s 6s 10s 15
输出复制
1 2 33 1 21 3 21 4 5 2 36 5 4 3 2 1
注意
在第一个测试用例中,所有元素的值都是明确给出的,因此唯一有效的排列是 $$$\{1, 2, 3\}$$$。
在第二个测试用例中,我们需要根据前缀反转计数重建排列:
- 对于位置 $$$2$$$,反转次数增加 $$$s_2 - s_1 = 1 - 0 = 1$$$。这意味着 $$$p_2$$$ 必须小于它之前的一个元素,因此 $$$p_1 \gt p_2$$$。
- 对于位置 $$$3$$$,反转次数增加 $$$s_3 - s_2 = 2 - 1 = 1$$$。这意味着 $$$p_3$$$ 比它之前的一个元素小。
在第三个测试用例中,我们给出 $$$p_1 = 1$$$ 和 $$$p_3 = 2$$$。 $$$p_2$$$ 唯一剩余的可用值是 $$$3$$$。我们可以验证前缀$$$p_1, p_2$$$(即$$$1, 3$$$)有$$$0$$$反转,完全满足条件$$$s_2 = 0$$$。因此,答案是$$$\{1, 3, 2\}$$$。
在第五个测试用例中,给定的 $$$s_i$$$ 值完全匹配 $$$\frac{i(i-1)}{2}$$$,这是长度为 $$$i$$$ 的前缀的最大可能反转次数。这意味着每个元素必须小于它之前的所有元素,这意味着排列是严格递减的。因此,答案是 $$$\{6, 5, 4, 3, 2, 1\}$$$。