← 返回题目列表

AtCoder · awtf2026algo_d

D. 调整交换 Lex Max

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

分数: 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).

在第二个测试用例中,最好不执行任何操作。