分数: 2500 点
问题陈述
给你排列 P 和 Q of (1,2,\ldots,N)。 在这里, P 按字典顺序不大于 Q.
您可以执行以下操作零次或多次。
- 选择两个相邻元素 P 并交换它们。这里,必须满足以下条件。
- P 运算后仍按字典顺序不大于 Q.
- 让 (x,y) 是被交换的两个值。这对 (x,y) 在之前的操作中从未被交换过。这里,顺序为 x,y 没关系。也就是说,一旦 (x,y) 已被交换,也没有 (x,y) 也不 (y,x) 可以再次交换。
找到字典顺序上最大的排列 P 到底能成不成。 每个输入的
解决 T 例。
约束
- 1 \leq T \leq 500000
- 2 \leq N \leq 10^6
- P 是一个排列 (1,2,\ldots,N).
- Q 是一个排列 (1,2,\ldots,N).
- P 按字典顺序不大于 Q.
- 总和 N 超过 T 案例最多 10^6.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个测试用例均按以下格式给出:
N P_1 P_2 \ldots P_N Q_1 Q_2 \ldots Q_N
输出
对于每个测试用例,输出所寻求的排列。
示例输入 1
6 3 1 2 3 3 1 2 3 2 3 1 3 1 2 4 3 1 4 2 4 2 3 1 4 2 3 4 1 3 4 1 2 4 1 3 4 2 1 4 2 3 5 4 2 5 3 1 4 2 5 3 1
示例输出 1
3 1 2 2 3 1 4 2 1 3 3 2 4 1 1 3 4 2 4 2 5 3 1
在第一个测试用例中,最好执行如下操作。
- 开始于 P=(1,2,3).
- 交换 (2,3),导致 P=(1,3,2).
- 交换 (1,3),导致 P=(3,1,2).
在第二个测试用例中,最好不执行任何操作。