#CW46. 复原排列(permutation)

复原排列(permutation)

题目描述

小 W 有一个 11 到 nn 的排列 pp。对于每个位置 ii,定义

si=#{(j,k)∣1≤j<k≤i, pj>pk}.s_i=\#\{(j,k)\mid 1\le j<k\le i,\ p_j>p_k\}.

小 Z 看到每个位置的一条信息:p x 表示 pi=xp_i=x,s x 表示 si=xs_i=x。这些信息由同一个排列产生,因此至少存在一个满足全部信息的排列。请输出任意一个满足条件的排列。

输入格式

第一行是整数 TT,表示测试用例数。

每个测试用例的第一行是整数 nn。接下来 nn 行按 i=1,2,…,ni=1,2,\dots,n 的顺序给出信息。每行包含一个字符 p 或 s,以及一个整数 xx:

  • p x:要求 pi=xp_i=x;
  • s x:要求前缀逆序对数 si=xs_i=x。

输出格式

对每个测试用例输出一行 nn 个整数,表示一个排列 pp。输出的排列必须同时满足输入中的所有信息。

本题答案不唯一,评测使用特殊校验:只要输出是合法的 1…n1\dots n 排列且满足全部信息即视为正确。

样例 1 输入

2
3
s 0
p 2
s 3
4
p 4
s 1
p 2
s 3

样例 1 输出

3 2 1
4 1 2 3

第二组数据中,前缀 [4,1][4,1] 有一个逆序对,前缀 [4,1,2,3][4,1,2,3] 有三个逆序对。

数据范围与子任务

保证 1≤T1\le T,1≤n≤2×1051\le n\le 2\times 10^5,且所有测试用例的 nn 之和不超过 2×1052\times 10^5。所有 p 信息中的 xx 属于 [1,n][1,n],所有 s 信息中的 xx 属于 [0,i(i−1)2]\left[0,\frac{i(i-1)}{2}\right],并且信息一定来自至少一个排列。

子任务 分值 测试点 额外限制
1 10 1∼21\sim 2 n≤8n\le 8,T≤10T\le 10
2 20 3∼63\sim 6 n≤1000n\le 1000,T≤10T\le 10
3 7∼107\sim 10 每条信息均为 s 类型
4 50 11∼2011\sim 20 无额外限制