Optimal Insertion
题意翻译
### 题目大意
给定两个序列 $a,b$,长度分别为 $n,m(1\leq n,m\leq 10^6)$。接下来将 $b$ 中的所有元素以**任意方式**插入序列 $a$ 中**任意位置**,请找出一种插入方式使结果序列中的逆序对数量最小化,并输出这个最小值。
**关于插入**:任意方式插入任意位置的示例如下。
例如 $a=\{1,2,3,4\},b=\{4,5,6\}$,则 $c=\{4,\underline1,5,\underline2,\underline3,\underline4,6\},\{\underline1,\underline2,6,5,\underline3,4,\underline4\}\dots$ 均为合法的插入方式。但你不能修改 $a$ 的顺序。
### 输入格式
本题多测(~~注意多测不清空爆零两行泪~~
第一行给定一个正整数 $t\ (1\leq t\leq 10^4)$ 表示数据组数.
接下来对于每组数据,第一行两个整数 $n,m\ (1\leq n,m\leq 10^6)$ 分别表示 $a,b$ 的长度。
第二行包括 $n$ 个整数,表示 $a$。
第三行包括 $m$ 个整数,表示 $b$。
保证 $1\leq a_i,b_i\leq 10^9,\ 1\leq \sum n,\sum m\leq 10^6$。
### 输出格式
对于每组数据一行一个整数,表示最小逆序对数。
题目描述
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 < j $ and $ c_i > c_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.
输出格式
For each test case, print one integer — the minimum possible number of inversions in the resulting array $ 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
说明
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] $ .