← 返回题目列表

Codeforces · 1893/B

B. 中性色调

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$,以及由 $$$m$$$ 整数组成的数组 $$$b$$$。

设$$$\text{LIS}(c)$$$表示数组$$$c$$$的最长递增子序列的长度。例如,$$$\text{LIS}([2, \underline{1}, 1, \underline{3}])$$$ = $$$2$$$, $$$\text{LIS}([\underline{1}, \underline{7}, \underline{9}])$$$ = $$$3$$$, $$$\text{LIS}([3, \underline{1}, \下划线{2},\下划线{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$$$ 组成,可能已重新排列。
- $$$\text{LIS}(c)$$$ 的值是所有合适数组 $$$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)$$$ 的值最小化。如果有多个答案,则可以输出其中任何一个。

示例

输入 #1

7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777

输出 #1

6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1

注意

在第一个测试用例中,$$$\text{LIS}(a) = \text{LIS}([6, 4]) = 1$$$。我们可以在$$$6$$$和$$$4$$$之间插入数字$$$5$$$,则$$$\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$$$。