P15907 [TOPC 2024] Cards

戴安娜是一名喜欢玩各种类型桌游的学生。今天，她收到了老师送的一副卡牌作为生日礼物！ 这副卡牌很特别：牌堆中有 $n$ 张牌，每张牌正面有一个数字，背面有另一个数字。正面或背面的每个数字都是 $1$ 到 $n$ 的整数。此外，正面的 $n$ 个数字互不相同，背面的 $n$ 个数字也互不相同。换句话说，正面和背面的数字分别是 $1$ 到 $n$ 的两个不同排列。 除了桌游，戴安娜对数学和计算机科学也很感兴趣。她在玩这些牌时，想到了排列中逆序对的概念。逆序对定义为满足 $i < j$ 且位置 $i$ 上的元素大于位置 $j$ 上的元素的有序对 $(i, j)$。换句话说，逆序对表示两个元素相对于它们的位置“顺序错误”的情况。一个排列的逆序对数为 $c$，表示其中可以找到 $c$ 个逆序对。 戴安娜想知道她是否能以某种顺序重新排列这些牌，使得正面排列的逆序对数与背面排列的逆序对数相同（她不能翻转或丢弃任何牌）。她一时解不出这个问题，因此希望听听你的解法。 形式化地，给定两个 $1$ 到 $n$ 的整数排列：$a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_n$。你需要找到另一个 $1$ 到 $n$ 的正整数排列 $p_1, p_2, \dots, p_n$，使得 $a' = [a_{p_1}, a_{p_2}, \dots, a_{p_n}]$ 和 $b' = [b_{p_1}, b_{p_2}, \dots, b_{p_n}]$ 的逆序对数相同。输出序列 $a'$ 和 $b'$。

输入的第一行包含一个整数 $n$，表示牌堆中卡牌的数量。输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 是第 $i$ 张牌正面的数字。输入的第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，其中 $b_i$ 是第 $i$ 张牌背面的数字。

如果无法重新排列卡牌以满足上述条件，则输出 **No**。否则，在第一行输出 **Yes**。然后在第二行输出 $n$ 个整数 $a'_1, a'_2, \dots, a'_n$，表示重新排列后卡牌正面的数字。在第三行输出 $n$ 个整数 $b'_1, b'_2, \dots, b'_n$，表示重新排列后卡牌背面的数字。 如果存在多种可能的解法，输出任意一种即可。

- $1 \le n \le 5 \times 10^5$ - $1 \le a_i \le n$，对于 $i \in \{1, 2, \dots, n\}$ - $1 \le b_i \le n$，对于 $i \in \{1, 2, \dots, n\}$ - 保证 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_n$ 都是 $1, 2, \dots, n$ 的排列。 翻译由 DeepSeek V3.2 完成