← 返回题目列表

Codeforces · 1883/G2

G2. 舞蹈(困难版)

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

这是问题的困难版本。唯一的区别是在这个版本中 $$$m \leq 10^9$$$。

给定两个整数数组 $$$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$$$, $$$1 \leq m \leq 10^9$$$) - 数组 $$$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 4
1
3 2
4 7
5 1 5
3 8 3 3
8 4
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

2
12
16
4

注意

在第一个测试用例中:

- 对于数组 $$$([1, 1], [3, 2])$$$,答案是 $$$0$$$。不需要对元素进行任何操作或重新排序。
- 对于数组 $$$([2, 1], [3, 2])$$$,答案是 $$$0$$$。可以重新排列第一个数组的元素以获得$$$[1, 2)$$$。无需任何操作。
- 对于数组 $$$([3, 1], [3, 2])$$$,答案是 $$$1$$$。元素 $$$3$$$ 可以从第一个数组中删除,元素 $$$2$$$ 可以从第二个数组中删除。
- 对于数组 $$$([4, 1], [3, 2])$$$,答案是 $$$1$$$。元素 $$$4$$$ 可以从第一个数组中删除,元素 $$$3$$$ 可以从第二个数组中删除。