P13296 [GCJ 2013 #2] Erdős–Szekeres

给定一个数列 $X$，其内容为 $(1, 2, \ldots, N)$。一个递增子序列是指这些数字中按递增顺序出现的某个子集；递减子序列则是按递减顺序出现的子集。例如，$(5, 7, 8)$ 是 $(4, 5, 3, 7, 6, 2, 8, 1)$ 的一个递增子序列。 大约 80 年前，两位数学家 Paul Erdős 和 George Szekeres 证明了一个著名结论：$X$ 一定存在长度至少为 $\sqrt{N}$ 的递增子序列，或长度至少为 $\sqrt{N}$ 的递减子序列。例如，$(4, 5, 3, 7, 6, 2, 8, 1)$ 有一个长度为 $4$ 的递减子序列 $(5, 3, 2, 1)$。 我正在教授组合数学课程，想通过实例“证明”这个定理。对于序列中每个 $X[i]$，我会计算两个值： - $A[i]$：包含 $X[i]$ 且以 $X[i]$ 为最大值的最长递增子序列的长度。 - $B[i]$：包含 $X[i]$ 且以 $X[i]$ 为最大值的最长递减子序列的长度。 我的证明关键在于，对于每个 $i$，$(A[i], B[i])$ 这对值都是不同的，这就意味着对于某个 $i$，$A[i]$ 或 $B[i]$ 至少有一个不小于 $\sqrt{N}$。对于上面的序列，所有 $A[i]$ 和 $B[i]$ 的值如下表： | $i$ | $X[i]$ | $A[i]$ | $B[i]$ | |:-:|:----:|:----:|:----:| | 0 | 4 | 1 | 4 | | 1 | 5 | 2 | 4 | | 2 | 3 | 1 | 3 | | 3 | 7 | 3 | 4 | | 4 | 6 | 3 | 3 | | 5 | 2 | 1 | 2 | | 6 | 8 | 4 | 2 | | 7 | 1 | 1 | 1 | 我曾经设计了一个很有趣的数列来演示这个事实，并且为每个 $i$ 计算了 $A[i]$ 和 $B[i]$，但后来却忘记了原始的数列是什么。现在，给定 $A[i]$ 和 $B[i]$，你能帮我还原出 $X$ 吗？ $X$ 应该是 $(1, 2, \ldots, N)$ 的某种排列。如果有多种可能的数列，请输出字典序最小的那一个。也就是说，$X[0]$ 应尽量小，如果还有多种方案，则 $X[1]$ 尽量小，依此类推。

输入的第一行为测试用例数 $T$。接下来有 $T$ 个测试用例，每个测试用例包含三行。 每个测试用例的第一行为一个整数 $N$。第二行为 $N$ 个正整数，依次为 $A[0], A[1], \dots, A[N-1]$。第三行为 $N$ 个正整数，依次为 $B[0], B[1], \dots, B[N-1]$。

对于每个测试用例，输出一行 `"Case #x: "`，后接 $X[0], X[1], \dots, X[N-1]$，用空格分隔。

**限制条件** * $1 \leq T \leq 30$ * 保证至少存在一个可行解 **小数据集（9 分，测试集 1 - 可见）** * $1 \leq N \leq 20$ **大数据集（15 分，测试集 2 - 隐藏）** * $1 \leq N \leq 2000$ 翻译由 ChatGPT-4.1 完成。