CF2239C Revival

考虑一个由 $ 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], $$$ 其中方括号表示[艾弗森括号](https://en.wikipedia.org/wiki/Iverson_bracket)（Iverson bracket）记号。 对于每个位置 $ 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'} $，表示 $ s_i = x $，其中 $ 0 \le x \le \frac{i(i-1)}{2} $。 $n$ 的总和不超过 $2\cdot 10^5$。 保证一定存在一个合法的排列。

对于每个测试用例，输出一行 $ n $ 个整数，表示排列 $ p $。如果存在多个合法排列，你可以输出任意一个。

在第一个测试用例中，所有元素的值都明确给出，因此唯一的合法排列是 $ \{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\}$。 在第三个测试用例中，已知 $ \{3, 1, 2\} $ 和 $ 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\} $。