Журнал обменов
Склад — длинный коридор, вдоль которого стоят n ячеек; ячейка j находится в pj метрах от двери. Сначала товар i лежит в ячейке i. За месяц за товаром i ходят от двери fi раз, а некоторые пары товаров собирают вместе: пару (a, b) — w раз, и каждый раз сборщик проходит расстояние между их ячейками. Цена раскладки — общий путь за месяц:
$$\sum_i f_i \cdot \mathrm{pos}(i) \; + \sum_{(a,\,b,\,w)} w \cdot \bigl|\mathrm{pos}(a) - \mathrm{pos}(b)\bigr|,$$где pos(i) — расстояние от двери до ячейки, в которой сейчас лежит товар i.
Раскладку улучшала программа отжига. Каждый принятый ею ход она записала в журнал: товары x и y поменялись ячейками. Сама цена в журнал не попала. Восстановите её: какой была цена в начале и после каждого обмена?
Вход
В первой строке n, m и q — число ячеек (и товаров), пар и записей журнала (2 ≤ n ≤ 20 000, 0 ≤ m ≤ 20 000, 1 ≤ q ≤ 20 000). Во второй строке p1, …, pn (0 ≤ pj ≤ 106), в третьей — f1, …, fn (0 ≤ fi ≤ 104). Дальше m строк a b w — пары товаров (a ≠ b, 1 ≤ w ≤ 104); одна пара не повторяется, и каждый товар входит не больше чем в 40 пар. Дальше q строк x y — обмены в порядке журнала; x и y могут совпадать, тогда ничего не меняется.
Выход
q + 1 целых чисел, каждое с новой строки: цену раскладки в начале и после каждого обмена.
Примеры
Пример 1
3 1 2 0 10 20 1 1 1 1 3 5 1 2 3 1
130 80 80
Пример 2
4 3 5 0 4 9 15 2 0 1 3 1 2 3 2 4 1 1 4 2 1 2 3 3 4 1 2 4 2 4
107 111 111 122 106 122
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Пересчитать цену заново после каждого обмена — это O(n + m) на запись журнала, а записей до 20 000: сотни миллионов операций. Что на самом деле меняется, когда два товара меняются ячейками?
2Подсказка 2
Меняются только слагаемые, где участвует x или y: два слагаемых «путь от двери» и пары этих двух товаров. Каждый товар входит не больше чем в 40 пар. А что с парой, если x и y сами образуют пару? И что, если x = y?
3Идея
Это та самая операция, на которой держится любой быстрый отжиг: изменение цены от хода считается по соседям хода, а не по всей задаче. Пусть до обмена товар x лежит на расстоянии px от двери, а y — на py. Тогда
Δ = fx(py − px) + fy(px − py) + Σ(x, z, w), z ≠ y w(|py − pos(z)| − |px − pos(z)|) + Σ(y, z, w), z ≠ x w(|px − pos(z)| − |py − pos(z)|).
Пару (x, y) пропускаем: после обмена между ними то же расстояние |px − py|. Если её не пропустить, формула посчитает её с позициями, где один из двоих уже «переехал», а другой ещё нет, — и ошибётся. Обмен товара с самим собой ничего не меняет, и его надо просто пропустить: формула с x = y тоже дала бы ноль, но только при условии, что пара (x, x) исключена — а такой пары и нет.
4Разбор
Храним pos — где лежит каждый товар, и для каждого товара список его пар с весами. Начальную цену считаем целиком, один раз. Для каждой записи журнала считаем Δ по формуле, меняем pos[x] и pos[y] местами и прибавляем Δ к цене. Цена доходит до 1015: в Go это int64, в Python — обычное целое.
Шестой тест — настоящий. 32 буквы «Войны и мира» стоят в одной строке клавиш через 19 мм; «за товаром ходят» столько раз, сколько встречается буква (делённое на 100), а пары — соседние буквы, которые встретились в тексте хотя бы 100 раз. Журнал — все 429 ходов, которые принял отжиг этой самой цены: она падает с 10 154 569 до 6 025 204.
4+Решение
5Сложность
O(n + m) на начальную цену и O(deg x + deg y) ≤ O(80) на запись журнала: всего O(n + m + 80q).
6Типичные ошибки
- Пересчёт всей цены. Верно, но на больших журналах в сотни раз дольше лимита.
- Пара (x, y) в обоих списках. Если не пропустить её, второй пример ломается с первой же записи: товары 1 и 2 — пара, и вместо 111 получается 87.
- Позиции меняют до подсчёта. Если сначала переставить pos, а потом считать Δ по «старым» позициям, получится ноль или удвоенная ошибка — порядок важен.
- 32 бита. В седьмом тесте цена около 2·1014, в int32 она не помещается.