Слить правки без сервера
Несколько человек правят общий документ, каждый в своей копии, без сервера. Документ — последовательность элементов, у каждого элемента свой номер — пара (c, r): счётчик и номер копии, где элемент создан. Из двух номеров больше тот, у кого больше c, а при равных c — больше r. Номер нового элемента всегда больше номеров всех элементов, о которых его копия знала в момент вставки.
Операции такие. I c r lc lr t — вставить элемент с номером (c, r) и значением t сразу после элемента (lc, lr); номер (0, 0) означает начало документа. D c r — удалить элемент (c, r). Операции приходят в копию в любом порядке, где элемент появляется раньше, чем его упоминают. Порядок вставок в одно место определяется так, чтобы все копии пришли к одному документу: если после одного и того же элемента вставили несколько элементов, то среди них раньше идёт элемент с бо́льшим номером — вместе со всем, что потом вставили после него.
Выведите документ, который получится после всех операций. Один из тестов — настоящая правка стиля главы базового курса этого сайта, поделённая между тремя редакторами: элемент — слово или кусок пробелов, его значение — номер слова в словаре.
Вход
В первой строке — число операций n (1 ≤ n ≤ 2·105). Дальше n операций в порядке получения. Все номера — целые от 0 до 109, значения элементов — целые от 1 до 106. Каждый элемент вставляется один раз и удаляется не больше одного раза.
Выход
Значения неудалённых элементов документа по порядку, через пробел.
В первом примере копия 1 печатает 10, 20, 30, а копия 2, уже зная о 10, — 40, 50 сразу после 10. Номер (3, 2) у элемента 40 больше номера (2, 1) у 20, поэтому 40 и всё, что вставлено после него, встаёт раньше 20. Затем 20 удаляется. Второй пример — те же операции в другом порядке, и документ тот же.
Примеры
Пример 1
6 I 1 1 0 0 10 I 2 1 1 1 20 I 3 1 2 1 30 I 3 2 1 1 40 I 4 2 3 2 50 D 2 1
10 40 50 30
Пример 2
6 I 1 1 0 0 10 I 3 2 1 1 40 I 2 1 1 1 20 I 4 2 3 2 50 D 2 1 I 3 1 2 1 30
10 40 50 30
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Вставлять «сразу после левого соседа» не получится: результат зависит от порядка прихода операций, а он у копий разный. Что лежит после левого соседа к моменту вставки и как понять, кого из этих элементов пропустить?
2Идея
Это RGA, растущий реплицированный массив. Вставку (e после x) делаем так: стоим на x и, пока следующий элемент имеет номер больше e, переходим к нему; затем вставляем e сразу за текущим. Почему это верно? Элементы с номером больше e, которые лежат после x, — это вставки после x, параллельные e и стоящие перед ним по правилу, вместе со всем, что вставили после них позже: у тех номера ещё больше, ведь их копия уже знала о предшественниках. Первый же элемент с номером меньше e должен идти после e: это либо параллельная вставка после x, которая уступает e, либо элемент, лежавший после x ещё до вставки e, — и в копии, где e создали, он тоже оказался после e.
Удаление ничего не сдвигает: элемент становится надгробием, остаётся в цепочке и по-прежнему служит соседом для чужих вставок, которые могли ссылаться на него. В выводе надгробия пропускаются.
3Разбор
Документ храним связным списком в словаре: номер → следующий номер, плюс словарь значений и множество удалённых. Вставка — прыжки по списку от левого соседа, удаление — отметка, вывод — проход от начала. Номера сравниваются как пары, сначала счётчик, потом копия.
На третьем тесте — настоящих правках трёх редакторов — документ сходится к той самой правке стиля, которую сделал один человек: 16 684 элемента. Конфликтов нет, потому что редакторы правили разные слова; там, где они меняют одно и то же слово по-разному, RGA оставит оба варианта рядом, и выбирать между ними придётся человеку.
3+Решение
4Сложность
Каждая вставка проходит мимо элементов, вставленных после её соседа с бо́льшими номерами; на правках людей таких почти нет, и вставка стоит O(1) в среднем. В худшем случае — много параллельных вставок в одно место — проход длиннее, но всё равно ограничен числом таких вставок. Память — O(n): удалённые элементы не исчезают.
5Типичные ошибки
- Вставлять сразу за соседом. Порядок двух параллельных вставок в одно место станет зависеть от порядка доставки: во втором примере ответ поменяется.
- Удалять по-настоящему. Если выкинуть удалённый элемент из списка, чужая вставка, пришедшая позже и ссылающаяся на него, потеряет место.
- Позиция вместо номера. Хранить документ массивом и искать соседа перебором — O(n) на операцию; шестой тест — восемьдесят тысяч вставок подряд.
Алгоритмы задачи
O(1) на операцию у счётчика и множества; вставка в текст — O(1) в среднем
2 задачи
DS
Структура данных
Связный список
Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов.
O(1) у известного узла
2 задачи