Optimal Insertion
Contest: Codeforces Round 751 (Div. 1)
Difficulty rating: 2300
Tags: data structures, divide and conquer, dp, greedy, sortings

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$$$.

Input format:
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.

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

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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]$$$.

Example input:
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

Example output:
0
4
6

Editorial:
Let's sort array $$$b$$$.
Let's define $$$p_i$$$ as the index of the array $$$a$$$, before which we should insert $$$b_i$$$. If $$$b_i$$$ should be inserted at the end of the array $$$a$$$, let's make $$$p_i = n + 1$$$.
Let's note, that all inserted elements should go in the sorted order in the optimal answer. If it is false and there exists $$$p_i > p_j$$$ for $$$i < j$$$, let's swap $$$b_i$$$ and $$$b_j$$$ in the answer. The number of inversions will decrease, a contradiction.
So $$$p_1 \leq p_2 \leq \ldots \leq p_m$$$. If we will find their values we will be able to restore an array after inserting elements.
Let's use "Divide and conquer" to find them. Let's write a recursive function $$$solve(l_i, r_i, l_p, r_p)$$$, that will find $$$p_i$$$ for all $$$l_i \leq i < r_i$$$, if it is known, that $$$p_i \in [l_p, r_p]$$$ for all such $$$i$$$. To find all values of $$$p$$$ we should call the function $$$solve(1, m + 1, 1, n + 1)$$$.
Realization of $$$solve(l_i, r_i, l_p, r_p)$$$:
• If $$$l_i \geq r_i$$$, we shouldn't do anything.
• Let $$$mid = \lfloor \frac{l_i + r_i}{2} \rfloor$$$. Let's find $$$p_{mid}$$$. The number of inversions with $$$b_{mid}$$$ will be (the number of $$$a_i > b_{mid}$$$ for $$$i < p_{mid}$$$) + (the number of $$$a_i < b_{mid}$$$ for $$$i \geq p_{mid}$$$). This sum differs by a constant from: (the number of $$$a_i > b_{mid}$$$ for $$$l_p \leq i < p_{mid}$$$) + (the number of $$$a_i < b_{mid}$$$ for $$$p_{mid} \leq i < r_p$$$). For this sum it is simple to find the minimal optimal $$$p_{mid}$$$ in $$$O(r_p - l_p)$$$.
• Let's make two recursive calls of $$$solve(l_i, mid - 1, l_p, p_{mid})$$$, $$$solve(mid + 1, r_i, p_{mid}, r_p)$$$, that will find all remaining values of $$$p$$$.
The complexity of this function will be $$$O((n+m)\log{m})$$$, because there will be $$$O(\log{m})$$$ levels of recursion and we will make $$$O(n+m)$$$ operations on each of them.
In the end, using the values $$$p_i$$$ we will restore the array and find the number of inversions in it.
Total complexity: $$$O((n+m)\log{(n+m)})$$$.
Also, there exist other correct solutions with the same complexity, using segment tree.