Медиана периода
Архив погоды хранит среднюю температуру за каждый из n дней. Климатологам нужны не средние, а порядковые характеристики: медиана месяца, самый холодный день лета, десятый по теплоте день периода. На каждый вопрос «какая температура k-я по возрастанию среди дней с l-го по r-й» нужно ответить быстро — вопросов десятки тысяч.
Три теста — настоящий архив: средняя температура Алматы за каждый день 1941–2025 годов по реанализу ERA5, в десятых долях градуса. В одном из них спрашивают медиану каждого месяца и каждого лета.
В примере за все семь дней по возрастанию: −40, −10, 10, 20, 20, 30, 50, и четвёртая — 20. Со второго по пятый день самая холодная — −10; третий день один, и его температура 50; с четвёртого по седьмой вторая по возрастанию — 10.
Вход
В первой строке n и q (1 ≤ n, q ≤ 40 000). Во второй — n целых температур, по модулю не больше 109. Дальше q строк по три целых l, r, k (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ r − l + 1).
Выход
Для каждого вопроса — k-я по возрастанию температура среди дней с l-го по r-й, по одной в строке.
Примеры
Пример 1
7 4 30 -10 50 20 20 -40 10 1 7 4 2 5 1 3 3 1 4 7 2
20 -10 50 10
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы период всегда начинался с первого дня, хватило бы дерева отрезков по значениям: в узле — сколько дней попало в его диапазон температур, и k-я находится спуском от корня. Как перейти от «первых r дней» к «дням с l-го по r-й»?
2Подсказка 2
Число дней периода в диапазоне температур — это число среди первых r дней минус число среди первых l − 1. Нужны все деревья «первых i дней» сразу, а хранить их копиями слишком дорого.
3Идея
Персистентное дерево отрезков по значениям: версия i — дерево первых i дней. Новая версия отличается от предыдущей одним днём, то есть только путём от корня к листу его температуры: этот путь копируется, остальное общее. Спуск ищет k-ю сразу в двух версиях, r и l − 1: в левом ребёнке дней периода countr − countl−1; если k не больше — идём влево, иначе вычитаем и идём вправо.
4Разбор
Температуры сжимаем в номера по возрастанию, чтобы дерево было по номерам, а не по диапазону до 109. Узлы держим в трёх массивах — левый ребёнок, правый, счётчик — и заводим узел 0, пустое дерево, на который ссылаются все пустые ветки: тогда версия 0 — это просто узел 0. Каждая вставка добавляет ⌈log₂ V⌉ + 1 узлов, где V — число разных температур. Массивы лучше выделить сразу на n·(⌈log₂ V⌉ + 1) + 1 узлов.
На архиве Алматы 505 разных температур, и все 31 047 версий занимают 310 тысяч узлов вместо 31 миллиона при копиях. Первый вопрос третьего теста — медиана января 1941 года: −3,3°.
4+Решение
5Сложность
O(n log V) на построение, O(log V) на вопрос, O(n log V) памяти.
6Типичные ошибки
- Версия l вместо l − 1. Разность версий r и l даёт дни с (l + 1)-го по r-й — первый день периода выпадает. Это
wrong.py. - Изменять старые узлы. Если при вставке поправить счётчик в узле прежней версии, а не в его копии, все старые версии тоже изменятся.
- Сортировать каждый период. Правильно, но 40 000 периодов по десятку тысяч дней — сотни миллионов операций.
Алгоритмы задачи
O(log n) на изменение и запрос
1 задача
DS
Структура данных
Дерево отрезков
Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n).
O(log n) на запрос и на изменение
2 задачи