← 返回题目列表

Codeforces · 2239/C

C. 复兴

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

考虑 $$$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$$$ 整数。

如果有多个有效排列,则可以输出其中任何一个。

示例

输入
复制

5
3
p 1
p 2
p 3
3
s 0
s 1
s 2
3
p 1
s 0
p 2
5
p 1
p 4
s 0
p 2
s 4
6
s 0
s 1
s 3
s 6
s 10
s 15

输出
复制

1 2 3
3 1 2
1 3 2
1 4 5 2 3
6 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$$$ 比它之前的一个元素小。
满足这些条件的唯一排列是 $$$\{3, 1, 2\}$$$。

在第三个测试用例中,我们给出 $$$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\}$$$。