Самый жаркий день
Справочная служба погоды отвечает на вопросы вида «когда было жарче всего с такого-то дня по такой-то»: какой день периода был самым жарким по среднесуточной температуре. Если таких дней несколько, называют самый ранний. Ряд не меняется, а вопросов — десятки тысяч.
Один из тестов — настоящая среднесуточная температура Алматы с 1 января 1941 года по 31 декабря 2025-го в десятых долях градуса, 31 046 дней, и вопросы о годах, летах, десятилетиях и случайных периодах.
Вход
В первой строке n и q (1 ≤ n ≤ 100 000, 1 ≤ q ≤ 50 000). Во второй — n целых чисел a1, …, an, |ai| ≤ 10⁹. Дальше q строк с числами l и r (1 ≤ l ≤ r ≤ n).
Выход
На каждый вопрос — строка с наименьшим i из [l, r], для которого ai — наибольшее из al, …, ar.
Примеры
Пример 1
16 5 231 261 264 255 223 217 220 212 217 226 241 266 299 313 282 271 3 14 1 4 5 10 16 16 2 3
14 3 10 16 3
Пример 2
5 4 5 7 7 1 7 1 5 3 5 4 4 4 5
2 3 4 5
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Ряд не меняется, а вопросов много: подойдёт разреженная таблица — максимум любого отрезка за два чтения. Но нужен не максимум, а день, где он достигается, причём самый ранний. Можно ли хранить в таблице день, а не температуру?
2Подсказка 2
Таблица работает, если склейка ассоциативна, коммутативна и повтор ей не вредит. Проверьте, так ли это для правила «лучше тот день, где жарче, а при равенстве — более ранний».
3Идея
Правило «жарче, а при равенстве раньше» — это максимум по паре (температура, −номер дня): у разных дней пары разные, и из любого набора дней правило выбирает ровно один. Значит, это обычный максимум, только по другому ключу, и перекрытие двух блоков ему не вредит. Строим таблицу над номерами дней с этим правилом и отвечаем на вопрос двумя клетками строки ⌊log₂(r − l + 1)⌋.
4Разбор
На Go таблица хранит номера дней, а функция better сравнивает их по температуре и по номеру. На Python каждую пару удобно упаковать в одно число: (t + 10⁹)·217 + (217 − 1 − i). Температура занимает старшие разряды, а номер дня — младшие, причём перевёрнутый, так что из двух равных температур больше ключ у более раннего дня. Тогда каждая строка таблицы строится одним вызовом map(max, …) над двумя сдвинутыми срезами предыдущей строки, а номер дня достаётся из младших 17 бит ответа. 217 = 131 072 больше любого n, поэтому номера не налезают на температуру.
4+Решение
5Сложность
Построение — O(n log n) времени и памяти, каждый вопрос — O(1). Для ста тысяч дней это 17 строк таблицы. Перебор отрезка на каждый вопрос — O(n): в четвёртом тесте 50 000 вопросов почти о всём ряде.
6Типичные ошибки
- Срез и
maxна каждый вопрос. Быстро на коротких периодах, но O(r − l), а вопросы о десятилетиях — это тысячи дней каждый. - Хранить в таблице только температуру. Максимум найдётся, а день — нет; искать его потом проходом по отрезку снова O(n).
- Не тот день при равенстве. Если сравнивать только температуру, из двух равных выберется любой. Во втором примере на первый вопрос ответ 2, а не 3 или 5; в шестом тесте все дни одинаковы, и ответ всегда l.
- Логарифм в плавающей точке. Для длин до 10⁵
floor(log2(L))верен, но привычка опасная: начиная с 2⁴⁹ − 1 логарифм числа чуть меньше степени двойки округляется до целого, и строка таблицы выходит на одну больше. Номер старшего бита надёжнее считать целочисленно:bit_length() − 1илиbits.Len − 1.