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

Задача

Разрез по меридиану

дерево поиска дерево двоичный поиск предподсчёт геоданные

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

Все ключи различны, все приоритеты различны, поэтому дерево определено однозначно. Третий и четвёртый тесты — 45 227 городов GeoNames от 10 000 жителей с приоритетом-населением и 12 392 города от 50 000 жителей с приоритетом-широтой. Ключ города там — долгота в тысячных долях градуса, умноженная на 100 000, плюс номер города, чтобы ключи не совпадали; меридианы в третьем тесте — каждый целый градус.

Вход

В первой строке n (1 ≤ n ≤ 10⁵). Дальше n строк x p — ключ и приоритет узла (|x| ≤ 10¹², 1 ≤ p ≤ 10¹⁸), в любом порядке. Затем q (1 ≤ q ≤ 10⁵) и q строк — меридианы m (|m| ≤ 10¹²).

Выход

Для каждого меридиана — сколько узлов пройдёт разрез исходного дерева по нему.

Примеры

Пример 1

Вход
5
10 5
20 9
30 7
40 3
50 8
7
5
15
25
30
35
45
60
Выход
2
2
3
3
4
4
2

Пример 2

Вход
4
1 1
2 2
3 3
4 4
4
0
1
3
5
Выход
4
4
3
1

Ограничения

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

Разбор

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

1Подсказка 1

Само дерево строится за O(n): ключи сортируются, а дальше работает стек правого края, как в статье. Но и тогда честный разрез на каждый меридиан проходит путь от корня вниз, а дерево с неслучайными приоритетами может быть палкой — в пятом тесте приоритет растёт вместе с ключом.

2Подсказка 2

Разрез по m идёт тем же путём, что поиск ключа m, которого в дереве нет, и кончается в пустой ссылке. Между какими двумя ключами по порядку находится эта пустая ссылка?

3Подсказка 3

Пусть a — наибольший ключ меньше m, b — наименьший ключ не меньше m. В дереве поиска из двух соседних по порядку ключей один всегда предок другого. Под каким из них висит пустая ссылка, в которой кончается разрез?

4Идея

Ответ для меридиана — глубина более глубокого из двух соседей a и b (если одного нет — глубина другого). Глубины всех узлов считаются один раз обходом дерева, соседи меридиана находятся двоичным поиском по отсортированным ключам. Всего O((n + q) log n).

5Разбор

Почему один сосед — предок другого. Ключи a и b соседние по порядку. По лемме из статьи a — предок b, если у a наибольший приоритет среди ключей от a до b, а между ними других ключей нет — значит, это просто сравнение приоритетов a и b: у кого больше, тот и предок. Можно и без леммы: пустая ссылка между a и b в дереве поиска одна — это правая ссылка a или левая ссылка b, — и путь поиска к ней проходит через обоих.

Сколько узлов пройдёт разрез. Разрез по m на каждом узле выбирает то же направление, что и поиск m: направо, если ключ меньше m, налево — если не меньше. Поиск ключа между a и b проходит через обоих и кончается в пустой ссылке под более глубоким из них. Значит, разрез проходит все узлы пути от корня до более глубокого соседа — их ровно столько, какова его глубина. Если меридиан левее всех ключей, соседа a нет, и путь кончается под самым левым узлом b; справа — зеркально.

Реализация. Сортируем узлы по ключу, строим дерево стеком: новый узел снимает со стека узлы с меньшим приоритетом — последний снятый становится его левым ребёнком, — и сам становится правым ребёнком вершины стека. Корень — дно стека. Глубины считаем обходом с явным стеком: дерево-палка из 10⁵ узлов не пройдёт рекурсией Python. Для каждого меридиана bisect_left находит место i, где keys[i − 1] < m ≤ keys[i], и ответ — max(глубина keys[i − 1], глубина keys[i]).

На городах с приоритетом-населением разрез по нулевому меридиану проходит 23 узла, а по 180-му меридиану, за которым ключей уже нет, — 12; в дереве с приоритетом-широтой разрезы длиннее, потому что и само дерево выше. В палке из пятого теста разрез у левого края проходит все 10⁵ узлов.

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

Сортировка — O(n log n), построение и глубины — O(n), каждый меридиан — O(log n) на двоичный поиск. Память O(n).

7Типичные ошибки
  • Честный разрез на каждый вопрос. Верно, но на палке из пятого теста это 10⁵ вопросов по 5·10⁴ шагов в среднем — 5·10⁹ шагов.
  • Глубина одного соседа. Путь кончается под более глубоким из двух, а не под тем, что левее.
  • Вставка по одному. Строить дерево вставками с поворотами — O(n) на вставку на той же палке.
  • Граница. Ключ, равный меридиану, уходит на восток: нужен первый ключ, не меньший m, а не больший.

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

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