Цена журнала
Сервер хранит адреса страниц в косом дереве поиска, ключ — номер адреса. Запросы приходят по одному. Посчитайте, сколько сравнений сделает дерево на всём журнале.
Запрос с ключом k обслуживается так. Поиск идёт от корня: сравнивает k с ключом узла и уходит влево, если k меньше, вправо, если больше; каждый посещённый узел — одно сравнение. Если ключ найден, это узел x. Если поиск упёрся в пустое место, туда добавляется новый лист с ключом k — это и есть x, а сравнений столько, сколько узлов посетили по дороге. В пустом дереве новый ключ просто становится корнем без сравнений.
Затем x поднимается в корень. Пока у x есть родитель p:
- если p — корень, один поворот вокруг ребра x–p;
- если x и p оба левые дети или оба правые, сначала поворот p вокруг его родителя, потом поворот x вокруг p;
- иначе два поворота x подряд: вокруг p, потом вокруг нового родителя.
Поворот поднимает узел на уровень выше, сохраняя порядок ключей: так устроено косое дерево.
Два теста — настоящие журналы веб-сервера Космического центра Кеннеди за июль 1995 года, где каждый адрес заменён его номером по алфавиту.
Во втором примере вставки 1, 2, 3, 4, 5 по возрастанию стоят по одному сравнению — с корнем, — и дерево вытягивается в путь. Повторный проход по возрастанию сначала дорог — до ключа 1 пять сравнений, — но подъём парами поворотов складывает путь вдвое, и всего выходит 19 сравнений.
Вход
В первой строке n (1 ≤ n ≤ 100 000) — число запросов. Во второй — n ключей, целые от 1 до 109.
Выход
Одно число — сколько сравнений сделает дерево на всех запросах.
Примеры
Пример 1
7 5 3 8 3 5 1 3
12
Пример 2
10 1 2 3 4 5 1 2 3 4 5
19
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Задача — честно реализовать дерево из условия. Подумайте, как хранить узлы, чтобы поворот был несколькими присваиваниями, и как найти родителя и деда.
2Подсказка 2
Можно ли поднимать x одиночными поворотами — проще и тоже в корень? Посчитайте на втором примере.
3Идея
У каждого узла четыре поля: ключ, левый ребёнок, правый, родитель. Поворот x вокруг родителя p перевешивает внутреннее поддерево x к p, делает p ребёнком x и ставит x на место p у деда. Подъём в корень — цикл из трёх случаев условия. Порядок поворотов в случае «оба левые» важен: сначала родитель, потом x. Именно он складывает длинный путь вдвое и даёт амортизированные O(log n) на запрос; одиночные повороты дают то же дерево только на коротких путях.
4Разбор
Узлы удобно держать в параллельных массивах и ссылаться на них номерами, где −1 — пустая ссылка. Поиск идёт от корня и добавляет лист, если ключа нет; сравнения считаются по посещённым узлам. Ответ может быть больше 231: в худшем случае — порядка n log n с константой, на тестах — около двух миллионов, но лучше сразу брать 64-битное число.
На журнале сервера запрос стоит в среднем около 6,9 сравнения, а сбалансированное дерево на тех же 2230 адресах тратило бы около десяти: популярные адреса держатся у корня. На тесте «по возрастанию, дважды» косое дерево тратит около трёх сравнений на запрос.
4+Решение
5Сложность
O(n log n) амортизированно — по лемме о доступе из статьи.
6Типичные ошибки
- Одиночные повороты. «Передвинуть в корень» поворотами вокруг родителя — то же самое только для коротких путей. На втором примере выходит 23 сравнения вместо 19, а на ключах по возрастанию дважды — порядка n2: длинный путь не складывается, и второй проход проходит его целиком на каждом запросе. Это
wrong.py. - Не тот порядок в случае «оба левые». Если поворачивать сначала x, а потом ещё раз x, получится тот же подъём одиночными поворотами.
- Забыть родителя. После поворота меняются три связи «вверх»: у x, у p и у среднего поддерева.