CF2239C.Revival

Consider a permutation $p$ of $1, 2, \ldots, n$. Let $s_i$ denote the number of inversions in the entire prefix $p_1, p_2, \ldots, p_i$, defined as:

s\_i = \\sum\_{1 \\le x \\lt y \\le i} \[p\_x \\gt p\_y\],

where the square parantheses denote the Iverson bracket notation.

For each position $i$ ($1 \le i \le n$), you are given a condition in the form of either $p_i = x$ or $s_i = x$. Your task is to reconstruct the original permutation $p$.

考虑 $1, 2, \ldots, n$ 的一个排列 $p$。令 $s_i$ 表示整个前缀 $p_1, p_2, \ldots, p_i$ 中的逆序对数量，定义为：

s\_i = \\sum\_{1 \\le x \\lt y \\le i} \[p\_x \\gt p\_y\],

其中方括号表示 Iverson bracket 记号。

对每个位置 $i$（$1 \le i \le n$），你将获得一个形如 $p_i = x$ 或 $s_i = x$ 的条件。你的任务是重构原始排列 $p$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

For each test case: The first line contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$). Each of the following $n$ lines contains a character $c$ ($c \in {\text{'p'}, \text{'s'}}$) and an integer $x$:

• If $c = \text{'p'}$, it denotes that $p_i = x$, where $1 \le x \le n$.
• If $c = \text{'s'}$, it denotes that $s_i = x$, where $0 \le x \le \frac{i(i-1)}{2}$.

The sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

It is guaranteed that a valid permutation always exists.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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'}$，表示 $s_i = x$，其中 $0 \le x \le \frac{i(i-1)}{2}$。

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

保证始终存在合法的排列。

For each test case, output $n$ integers representing the permutation $p$.

If there are multiple valid permutations, you can output any of them.

对于每个测试用例，输出 $n$ 个整数，表示排列 $p$。

如果存在多个合法的排列，你可以输出其中任意一个。

In the first test case, the values of all elements are explicitly given, so the unique valid permutation is ${1, 2, 3}$.

In the second test case, we need to reconstruct the permutation from the prefix inversion counts:

• For position $2$, the number of inversions increases by $s_2 - s_1 = 1 - 0 = 1$. This means $p_2$ must be smaller than exactly one element before it, so $p_1 \gt p_2$.
• For position $3$, the number of inversions increases by $s_3 - s_2 = 2 - 1 = 1$. This means $p_3$ is smaller than exactly one element before it.

The only permutation satisfying these conditions is ${3, 1, 2}$.

In the third test case, we are given $p_1 = 1$ and $p_3 = 2$. The only remaining available value for $p_2$ is $3$. We can verify that the prefix $p_1, p_2$ (which is $1, 3$) has $0$ inversions, perfectly satisfying the condition $s_2 = 0$. Thus, the answer is ${1, 3, 2}$.

In the fifth test case, the given $s_i$ values perfectly match $\frac{i(i-1)}{2}$, which is the maximum possible number of inversions for a prefix of length $i$. This implies that every element must be smaller than all elements before it, meaning the permutation is strictly decreasing. Hence, the answer is ${6, 5, 4, 3, 2, 1}$.

在第一个测试用例中，所有元素的值均被显式给出，因此唯一有效的排列是 ${1, 2, 3}$。

在第二个测试用例中，我们需要根据前缀逆序数（prefix inversion counts）重构排列：

• 在位置 $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}$。