← 返回题目列表

Codeforces · 1883/G1

G1. 舞蹈(简单版)

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

这是问题的简单版本。唯一的区别是在此版本中 $$$m = 1$$$。

给定两个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$b_1, b_2, \ldots, b_n$$$。在应用任何操作之前,您可以根据需要对每个数组的元素重新排序。然后,在一项操作中,如果数组不为空,您将执行以下两项操作:

- 从数组 $$$a$$$ 中选择任意元素并将其删除(所有剩余元素都转移到新数组 $$$a$$$ 中),
- 从数组 $$$b$$$ 中选择任意元素并将其删除(所有剩余元素都将转移到新数组 $$$b$$$ 中)。

设 $$$k$$$ 为两个数组的最终大小。您需要找到对于所有 $$$1 \leq i \leq k$$$ 满足 $$$a_i < b_i$$$ 所需的最少操作数。

这个问题太简单了,所以问题作者决定让它变得更有挑战性。您还将获得一个正整数 $$$m$$$。现在,您需要找到 $$$m$$$ 数组对 $$$(c[i], b)$$$ 问题的答案之和,其中 $$$1 \leq i \leq m$$$。数组 $$$c[i]$$$ 是从 $$$a$$$ 获取的,如下所示:

- $$$c[i]_1 = i$$$,
- $$$c[i]_j = a_j$$$,对于 $$$2 \leq j \leq n$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) - 输入数据的组数。接下来是他们的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$m = 1$$$) - 数组 $$$a$$$ 和 $$$b$$$ 的大小以及元素 $$$a_1$$$ 值的约束。

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

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

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出所有数组对 $$$(c_i, b)$$$ 的最小操作总数。

示例

输入 #1

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

输出 #1

0
1
4
4

注意

在数组对 $$$([1, 1], [3, 2])$$$ 的第一个测试用例中,答案是 $$$0$$$。不需要对元素进行任何操作或重新排序。