CS
Задачник Базовый курс EN

Задача

Все версии текста

дерево редакторы текста контроль версий случайность

Редактор хранит всю историю текста: каждая правка создаёт новую версию, а старые остаются, и править можно любую из них — так появляются ветки, как в системе контроля версий. Версия 0 — исходный текст. Обращения бывают трёх видов:

  • + v p s — взять версию v, вставить строку s перед знаком с номером p (знаки нумеруются с нуля; p может равняться длине — тогда в конец) и сохранить результат как следующую по номеру версию;
  • - v p k — взять версию v, удалить k знаков начиная с p-го и сохранить как следующую версию;
  • ? v p — вывести знак с номером p в версии v.

Новые версии нумеруются по порядку появления: первая правка создаёт версию 1, вторая — 2 и так далее; вопросы версий не создают. Тексты в тестах — «Война и мир» в английском переводе, где пробелы заменены на _, а переводы строки убраны; вставляемые слова взяты оттуда же.

В примере версия 1 — NatashaIlyinichna__Rostova, её седьмой знак — I; версия 2 — та же без первых восьми знаков, начинается с l; а версия 0 по-прежнему начинается с N.

Вход

В первой строке исходный текст: от 1 до 300 000 видимых знаков ASCII без пробелов. Во второй — число обращений q (1 ≤ q ≤ 20 000). Дальше q строк с обращениями; вставляемая строка — от 1 до 100 видимых знаков ASCII без пробелов. Все обращения корректны: версия существует, позиции лежат внутри текста.

Выход

Ответы на вопросы, по одному знаку в строке.

Примеры

Пример 1

Вход
Natasha_Rostova
5
+ 0 7 Ilyinichna_
? 1 7
- 1 0 8
? 2 0
? 0 0
Выход
I
l
N

Ограничения

Время · Python
5000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Хранить каждую версию копией не выйдет: двадцать тысяч копий по триста тысяч знаков — шесть гигабайт. Как сделать так, чтобы новая версия делила со старой всё, чего правка не коснулась?

2Подсказка 2

Текст как дерево кусков с неявным ключом — верёвка. Вставка и удаление — это разрезы и склейки дерева. А если разрезы и склейки никогда не меняют существующие узлы, а создают новые, старая версия остаётся целой.

3Идея

Верёвка на декартовом дереве по неявному ключу: в узле кусок текста (до 256 знаков), приоритет и длина поддерева. Операции split (первые k знаков и остальное) и merge (склейка двух деревьев) пишутся так, чтобы вместо изменения узла создавать его копию с новыми ссылками — копирование пути. Тогда каждая правка создаёт O(log n) новых узлов и, может быть, режет один кусок, а все версии живут одновременно: версия — это корень. Знак с номером p ищется спуском по длинам поддеревьев.

4Разбор

Вставка: разрезать версию v в позиции p, склеить левую часть, дерево из кусков s и правую часть. Удаление: разрезать в p, у правой части отрезать первые k знаков и выбросить, склеить остальное. Если разрез приходится внутрь куска, кусок делится на два новых узла. Приоритеты — случайные; копия узла сохраняет его приоритет, поэтому форма дерева остаётся правильной.

Память — O(n/256 + q log n) узлов плюс разрезанные куски. В Python удобно держать узлы неизменяемыми кортежами: тогда изменить общий узел просто нельзя.

4+Решение
5Сложность

O(log n + 256) на правку и O(log n) на вопрос в среднем по случайным приоритетам.

6Типичные ошибки
  • Копия на каждую версию. Правильно, но памяти — сумма длин всех версий. Это wrong.py: превышает память.
  • Изменять узлы при разрезе. Обычный split переписывает ссылки в существующих узлах — и старые версии, которые их делят, тихо меняются. Ответы на вопросы о старых версиях становятся неверными.
  • Новые приоритеты у копий. Если при копировании узла выдать ему новый случайный приоритет, порядок «приоритет родителя больше» нарушится, и merge перестанет держать дерево сбалансированным.

Алгоритмы задачи

DS Структура данных Верёвка Текст кусками в листьях дерева: вставка и удаление в середине — путь к листу и один кусок; номер строки — по счётчикам в узлах. O(log n + C) на вставку, удаление, доступ 1 задача DS Структура данных Персистентные структуры Каждое изменение — новая версия, старые живы; копируется только путь от корня. Медиана любого периода — разность двух версий. O(log n) на изменение и запрос 1 задача DS Структура данных Декартово дерево Ключ и случайный приоритет: глубина O(log n) в среднем, split и merge, массив с разворотом куска за O(log n). O(log n) в среднем на поиск, вставку, удаление, split и merge 1 задача
Каталог алгоритмов