Задача №114750. Оптимальная вставка
У вас есть два массива \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_m\), состоящие из целых чисел.
Вы должны вставить все элементы массива \(b\) в массив \(a\) в произвольные места. В результате получится массив \(c_1, c_2, \ldots, c_{n+m}\) размера \(n + m\).
Обратите внимание, что элементы массива \(a\) переставлять нельзя, а элементы массива \(b\) можно вставлять куда угодно (в начало, между двумя соседними элементами массива \(a\), в конец) и между собой они могут быть расположены в произвольном порядке.
Какое минимальное количество инверсий в массиве \(c\) может быть? Напомним, что инверсией называется пара индексов \((i, j)\), такая что \(i < j\) и \(c_i > c_j\).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится целое число \(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\).
Для каждого набора входных данных выведите одно целое число — минимальное количество инверсий, которое может получиться в массиве \(c\) при вставке.
Варианты оптимальных вставок для всех наборов входных данных (жирным выделены элементы массива \(a\)):
- В первом наборе входных данных можно сделать \(c = [\textbf{1}, 1, \textbf{2}, 2, \textbf{3}, 3, 4]\).
- Во втором наборе входных данных можно сделать \(c = [1, 2, \textbf{3}, \textbf{2}, \textbf{1}, 3]\).
- В третьем наборе входных данных можно сделать \(c = [\textbf{1}, 1, \textbf{3}, 3, \textbf{5}, \textbf{3}, \textbf{1}, 4, 6]\).
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
0 4 6