CF1893B Neutral Tonality

给定一个包含 $n$ 个整数的数组 $a$，以及一个包含 $m$ 个整数的数组 $b$。 记 $\text{LIS}(c)$ 表示数组 $c$ 的最长上升子序列（Longest Increasing Subsequence）的长度。例如，$\text{LIS}([2, \underline{1}, 1, \underline{3}]) = 2$，$\text{LIS}([\underline{1}, \underline{7}, \underline{9}]) = 3$，$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}]) = 3$。 你需要将 $b_1, b_2, \ldots, b_m$ 插入到数组 $a$ 中，插入的位置和顺序可以任意。插入后得到的新数组为 $c_1, c_2, \ldots, c_{n+m}$。你需要选择插入的位置，使得 $\text{LIS}(c)$ 的值最小。 形式化地说，你需要找到一个数组 $c_1, c_2, \ldots, c_{n+m}$，同时满足以下条件： - 数组 $a_1, a_2, \ldots, a_n$ 是数组 $c_1, c_2, \ldots, c_{n+m}$ 的一个子序列。 - 数组 $c_1, c_2, \ldots, c_{n+m}$ 由 $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_m$ 这 $n+m$ 个数（顺序可以重新排列）组成。 - 在所有满足上述条件的数组 $c$ 中，$\text{LIS}(c)$ 的值最小。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$，表示测试用例的组数。 每组测试用例的第一行包含两个整数 $n, m$ $(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$，分别表示数组 $a$ 和数组 $b$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$，表示数组 $a$ 的元素。 第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$ $(1 \leq b_i \leq 10^9)$，表示数组 $b$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$m$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出 $n + m$ 个数，表示最终得到的数组 $c_1, c_2, \ldots, c_{n+m}$，使得 $\text{LIS}(c)$ 的值最小。如果有多种方案，输出任意一种均可。

在第一个测试用例中，$\text{LIS}(a) = \text{LIS}([6, 4]) = 1$。我们可以将 $5$ 插入到 $6$ 和 $4$ 之间，此时 $\text{LIS}(c) = \text{LIS}([6, 5, 4]) = 1$。 在第二个测试用例中，$\text{LIS}([\underline{1}, 7, \underline{2}, \underline{4}, \underline{5}]) = 4$。插入后，$c = [1, 1, 7, 7, 2, 2, 4, 4, 5, 5]$。很容易看出 $\text{LIS}(c) = 4$。可以证明无法使 $\text{LIS}(c)$ 小于 $4$。 由 ChatGPT 4.1 翻译