Задача №115197. Почти наверное
Давайте скажем, что два мультимножества равны почти наверное , если они равны с точностью до одного элемента. То есть, чтобы можно было изменить не более одного элемента в первом множестве так, чтобы они стали равны. Например, мультимножества \(\{ 1, 1, 2 \}\) и \(\{ 1, 2, 3\}\) равны почти наверное , \(\{1, 1, 1 \}\) и \(\{ 1, 1, 1 \}\) равны почти наверное , а \(\{ 1, 2, 3 \}\) и \(\{ 3, 4, 5 \}\) не равны почти наверное .
Мальчику Васе очень понравилось это определение и он сразу же придумал про него задачу.
У Васи есть два массива \(a\) и \(b\), причем \(a_i \ge b_i\) для всех \(i\) от \(1\) до \(n\). Вася может применять сколько угодно (возможно ноль) раз к массиву \(a\) следующую операцию: выбрать любой индекс \(i\) (\(1 \le i \le n\)) и вычесть 1 из \(a_i\). При этом массив \(b\) Вася не меняет.
Вася быстро понял, какая последовательность операций нужна, чтобы мультимножество значений массивов \(a\) и \(b\) стали равны почти наверное . Поэтому Вася усложнил задачу — теперь для каждого префикса этих массивов он хочет узнать, какое минимальное количество операций нужно применить, чтобы префиксы массивов стали равны почти наверное .
Более формально, для каждого \(k\) от \(1\) до \(n\), Вася хочет взять элементы \(a_1, a_2, \ldots, a_k\), а также элементы \(b_1, b_2, \ldots, b_k\). Вася хочет знать, какое минимальное количество операций необходимо сделать, чтобы мультимножества этих элементов стали равны почти наверное . Обратите внимание, что задача для каждого \(k\) решается независимо .
Каждый тест состоит из одного или нескольких наборов входных данных. В первой строке содержится одно целое число \(t\) (\(1 \le t \le 100\,000\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число \(n\) (\(1 \le n \le 200\,000\)) — размер массивов \(a\) и \(b\).
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1,\ a_2,\ \ldots,\ a_n\) (\(1 \le a_i \le 10^9\)) — элементы массива \(a\).
Третья строка каждого набора входных данных содержит \(n\) целых чисел \(b_1,\ b_2,\ \ldots,\ b_n\) (\(1 \le b_i \le a_i\)) — элементы массива \(b\).
Обозначим за \(N\) сумму \(n\) по всем наборам входных данных в одном тесте. Гарантируется, что \(N \le 200\,000\).
Для каждого набора входных данных выведите \(n\) чисел, каждое из которых является ответом на задачу для каждой возможной длины префикса. Можно показать, что ответ всегда существует.
Рассмотрим первый набор входных данных в первом примере.
- Для префикса длины \(1\) нужно ничего не делать.
- Для префикса длины \(2\) нужно один раз уменьшить \(a_1 = 3\) на единицу, после этого \(a\) будет равен \([2, 4]\), \(b\) будет равен \([1, 2]\) и они равны почти наверное .
Рассмотрим третий набор входных данных в первом примере.
- Для префикса длины \(1\) нужно ничего не делать.
- Для префикса длины \(2\) нужно четыре раза уменьшить \(a_2 = 17\) на единицу, после этого префикс \(a\) будет равен \([11, 13]\), префикс \(b\) будет равен \([1, 13]\) и они равны почти наверное .
- Для префикса длины \(3\) нужно один раз уменьшить \(a_1 = 11\) на единицу, и один раз уменьшить \(a_3 = 14\) на единицу, после этого \(a\) будет равен \([10, 17, 13]\), \(b\) будет равен \([1, 13, 11]\) и они равны почти наверное .
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||
| Группа | Баллы | \(N\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 16 | \(N \leqslant 100\) | 0 | – |
| 2 | 13 | \(N \leqslant 500\) | 0, 1 | – |
| 3 | 24 | \(N \leqslant 3000\) | 0 – 2 | – |
| 4 | 13 | – | – | \(a_i \lt b_{i + 1}\) |
| 5 | 14 | – | 4 | \(a_i \leqslant a_{i + 1}, b_i \leqslant b_{i + 1}\) |
| 6 | 20 | – | 0 – 5 | Offline-проверка. |
Можно показать, что все тесты четвёртой группы удовлетворяют ограничениям пятой группы.
4 2 3 4 1 2 2 3 4 1 3 3 11 17 14 1 13 10 4 100 11 50 42 30 1 20 5
0 1 0 0 0 4 2 0 10 30 48
3 4 2 4 5 12 1 3 4 10 4 3 5 8 20 1 2 6 7 4 4 4 4 4 1 2 3 4
0 1 1 3 0 1 3 6 0 2 3 3