CF1883G2 Dances (Hard Version)

这是该问题的困难版本。唯一的区别在于本版本中 $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, 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$。 由 ChatGPT 4.1 翻译