Это сложная версия задачи. Единственное различие состоит в том, что в этой версии \(m \leq 10^9\).
Вам даны два массива целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\). До начала применения операций вы можете переупорядочить элементы каждого из массивов как угодно. Дальше за одну операцию вы делаете оба следующих действия, если массивы не пусты:
- Выбрать любой элемент из массива \(a\) и удалить его (все остальные элементы в том же порядке сдвигаются в один новый массив \(a\)),
- Выбрать любой элемент из массива \(b\) и удалить его (все остальные элементы в том же порядке сдвигаются в один новый массив \(b\)).
Пусть \(k\) — итоговый размер обоих массивов. Вам нужно найти наименьшее количество операций, чтобы выполнялось \(a_i < b_i\) для всех \(1 \leq i \leq k\).
Эта задача была слишком проста и автор задачи решил ее усложнить. Вам также дано натуральное число \(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\).
Выходные данные
Для каждого набора входных данных выведите суммарное количество наименьших операций по всем парам массивов \((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\) из второго.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 4
1
3 2
4 7
5 1 5
3 8 3 3
8 4
4 3 3 2 2 1 1
1 1 1 1 3 3 3 3
9 1
9 2 8 3 7 4 6 5
1 2 3 2 1 4 5 6 5
|
2
12
16
4
|