Высота без дерева
В обычное двоичное дерево поиска, без всякой балансировки, по очереди вставляют ключи. Каждый новый ключ спускается от корня: если он меньше ключа в узле — налево, если больше — направо, и становится листом там, где нужной ветки нет. Перед вставкой известен весь список ключей. Узнайте, какой высоты вырастет дерево и сколько всего сравнений сделают вставки: каждый ключ сравнивается со всеми узлами на пути от корня до своего места.
Высота — число узлов на самом длинном пути от корня до листа: у дерева из одного узла она равна 1. Третий и четвёртый тесты — все 19 073 землетрясения силой от 5 за 2015–2025 годы из каталога USGS в том порядке, в каком они случились; ключ — место толчка по глубине очага (в третьем тесте) или по силе (в четвёртом), равные значения упорядочены по времени.
Вход
В первой строке n (1 ≤ n ≤ 2·10⁵). Во второй — перестановка чисел от 1 до n: ключи в порядке вставки.
Выход
Два числа: высота дерева и общее число сравнений при всех вставках.
Примеры
Пример 1
5 3 1 4 5 2
3 6
Пример 2
5 1 2 3 4 5
5 10
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Построить дерево и вставлять честно — верно, но вставка стоит столько сравнений, какова глубина нового узла. Ключи по возрастанию дают палку из 2·10⁵ узлов и 2·10¹⁰ сравнений. Ответ в этом случае можно сосчитать и без дерева. А в общем?
2Подсказка 2
Пусть ключ x вставляется, когда в дереве уже есть какие-то ключи. Посмотрите на ближайший меньший ключ a и ближайший больший b среди них. Где в дереве окажется x относительно a и b?
3Подсказка 3
Новый узел становится ребёнком a или b — того из них, кто вставлен позже, а он и глубже. Остаётся для каждого ключа узнать его соседей по значению в момент вставки. Попробуйте идти по вставкам с конца.
4Идея
Глубина нового ключа равна 1 + max(глубина a, глубина b), где a и b — его соседи по значению среди уже вставленных. Соседей для всех ключей находит связный список: выстроим все ключи по возрастанию и будем вынимать их в порядке, обратном вставке. В момент, когда вынимается x, в списке остались ровно те ключи, что вставлены раньше него, и его соседи в списке — нужные a и b.
5Разбор
Почему ребёнок именно позднего соседа. Пусть a вставлен раньше b. Когда вставляли b, он прошёл мимо a: между ними не было ключей, поэтому b на каждом узле выше a шёл туда же, куда шёл бы a, а у самого a повернул направо. Значит, b лежит в правом поддереве a, ниже его. Ключ x между ними идёт по тому же пути до b, у b поворачивает налево — и левой ветки у b нет: ключ в ней лежал бы между a и b. Так x становится левым ребёнком b, и его глубина на единицу больше, чем у b, более глубокого из соседей. Если соседа с одной стороны нет, считаем его глубину нулём; первый ключ получает глубину 1.
Список — массивы prev и next по значениям от 0 до n + 1, где 0 и n + 1 — стражи. Проходим перестановку с конца: запоминаем соседей ключа и вынимаем его, связав соседей друг с другом. Потом проходим перестановку с начала и считаем глубины по формуле: высота — их максимум, сравнений — сумма глубин без единицы. Сумма доходит до 2·10¹⁰ — в Go нужен int64.
На третьем тесте высота 8350: у 8349 толчков в каталоге глубина ровно 10 км — такое значение USGS ставит, когда глубину определить не удалось, — и все они выстраиваются в цепочку.
5+Решение
6Сложность
O(n) времени: два прохода по перестановке, каждый шаг — O(1). Память O(n). Можно и за O(n log n): соседей по значению в момент вставки находит любое упорядоченное множество, но тогда в Python понадобится сбалансированное дерево, которого в стандартной библиотеке нет.
7Типичные ошибки
- Честная вставка. Шестой, седьмой и восьмой тесты — возрастающие ключи, убывающие и «зигзаг» 1, n, 2, n − 1, …: высота 2·10⁵, работы 2·10¹⁰.
- Рекурсия. Даже на третьем тесте дерево глубиной в восемь тысяч узлов, и рекурсивная вставка упрётся в предел глубины Python.
- Глубина более раннего соседа. Новый узел висит под более поздним, то есть более глубоким соседом: max, а не глубина a или b по выбору.
- 32-битная сумма. На шестом тесте сравнений 19 999 900 000.
Алгоритмы задачи
O(h): от O(log n) до O(n)
2 задачи
DS
Структура данных
Связный список
Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов.
O(1) у известного узла
2 задачи