← 返回题目列表

Codeforces · 1601/C

C. 最佳插入

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

给定两个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$b_1, b_2, \ldots, b_m$$$。

您需要以任意方式将 $$$b$$$ 的所有元素插入 $$$a$$$ 中。结果你将得到一个大小为 $$$n + m$$$ 的数组 $$$c_1, c_2, \ldots, c_{n+m}$$$。

请注意,您不能更改 $$$a$$$ 中元素的顺序,但可以在任意位置插入 $$$b$$$ 中的元素。它们可以插入到开头、$$$a$$$ 的任何元素之间或末尾。此外,$$$b$$$ 的元素可以以任何顺序出现在结果数组中。

结果数组 $$$c$$$ 中可能的最小反转次数是多少?回想一下,反转是一对索引 $$$(i, j)$$$,使得 $$$i < j$$$ 且 $$$c_i > c_j$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 10^6$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$)。

保证一次输入中所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。所有测试用例的 $$$m$$$ 总和也不超过 $$$10^6$$$。

输出

对于每个测试用例,打印一个整数 - 结果数组 $$$c$$$ 中可能的最小反转数。

示例

输入 #1

3
3 4
1 2 3
4 3 2 1
3 3
3 2 1
1 2 3
5 4
1 3 5 3 1
4 3 6 1

输出 #1

0
4
6

注意

下面给出了获得每个示例测试用例的最佳答案的解决方案($$$a$$$ 的元素带有下划线)。

- 在第一个测试用例中,$$$c = [\underline{1}, 1, \underline{2}, 2, \underline{3}, 3, 4]$$$。
- 在第二个测试用例中,$$$c = [1, 2, \underline{3}, \underline{2}, \underline{1}, 3]$$$。
- 在第三个测试用例中,$$$c = [\underline{1}, 1, 3, \underline{3}, \underline{5}, \underline{3}, \underline{1}, 4, 6]$$$。