CF1601C.Optimal Insertion

You are given two arrays of integers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_m$.

You need to insert all elements of $b$ into $a$ in an arbitrary way. As a result you will get an array $c_1, c_2, \ldots, c_{n+m}$ of size $n + m$.

Note that you are not allowed to change the order of elements in $a$, while you can insert elements of $b$ at arbitrary positions. They can be inserted at the beginning, between any elements of $a$, or at the end. Moreover, elements of $b$ can appear in the resulting array in any order.

What is the minimum possible number of inversions in the resulting array $c$? Recall that an inversion is a pair of indices $(i, j)$ such that $i \lt j$ and $c_i \gt c_j$.

给你两个整数数组 $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$ 中可以以任意顺序出现。

在所有可能的插入方案中，最终数组 $c$ 所含逆序对的最小数量是多少？
回忆一下，一个逆序对是指满足 $i \lt j$ 且 $c_i \gt c_j$ 的下标对 $(i, j)$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^6$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).

The third line of each test case contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \leq b_i \leq 10^9$).

It is guaranteed that the sum of $n$ for all tests cases in one input doesn't exceed $10^6$. The sum of $m$ for all tests cases doesn't exceed $10^6$ as well.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print one integer — the minimum possible number of inversions in the resulting array $c$.

对于每个测试用例，输出一个整数——结果数组 $c$ 中可能的最少逆序对数量。

Below is given the solution to get the optimal answer for each of the example test cases (elements of $a$ are underscored).

• In the first test case, $c = [\underline{1}, 1, \underline{2}, 2, \underline{3}, 3, 4]$.
• In the second test case, $c = [1, 2, \underline{3}, \underline{2}, \underline{1}, 3]$.
• In the third test case, $c = [\underline{1}, 1, 3, \underline{3}, \underline{5}, \underline{3}, \underline{1}, 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]$。