Поправки к ряду
Климатолог выравнивает ряд суточных температур. Когда метеостанцию переносят или меняют на ней прибор, в ряду появляется скачок, не связанный с погодой, и все показания за период до или после перемены сдвигают на поправку. Поправки приходят одна за другой, а между ними коллегам нужны ответы: какой день периода был самым холодным и какой — самым тёплым, с учётом всех поправок, внесённых к этому моменту.
Два теста — настоящая среднесуточная температура Алматы с 1 января 1941 года по 31 декабря 2025-го в десятых долях градуса, 31 046 дней: в одном поправки к годам и десятилетиям перемешаны с вопросами о зимах, летах и случайных периодах, в другом только вопросы.
Вход
В первой строке n и q (1 ≤ n ≤ 100 000, 1 ≤ q ≤ 50 000). Во второй — n целых чисел a1, …, an, |ai| ≤ 10⁹. Дальше q строк, в каждой одна операция:
+ l r d— прибавить d к каждому из чисел al, …, ar (|d| ≤ 10⁹);? l r— вопрос о числах al, …, ar.
Везде 1 ≤ l ≤ r ≤ n.
Выход
На каждый вопрос — строка из двух чисел через пробел: наименьшее и наибольшее из al, …, ar с учётом всех поправок, которые были до этого вопроса.
Примеры
Пример 1
16 6 -21 -10 -16 -72 -115 -133 -154 -191 -182 -116 -68 -68 -99 -88 -62 -67 ? 6 9 + 4 13 50 ? 6 9 ? 1 16 + 1 8 -10 ? 4 5
-191 -133 -141 -83 -141 -10 -75 -32
Пример 2
1 4 7 ? 1 1 + 1 1 -3 + 1 1 -3 ? 1 1
7 7 1 1
Ограничения
- Время · Python
- 15000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы поправок не было, хватило бы разреженной таблицы или дерева отрезков. Если бы поправки касались одного дня, дерево меняло бы лист и путь до корня. Поправка к отрезку — это тысячи листьев. Нужно ли знать о ней каждому?
2Подсказка 2
Прибавка ко всем дням узла сдвигает его минимум и максимум на ту же величину — детей для этого спрашивать не нужно. Узел, целиком лежащий в отрезке поправки, может исправить свой ответ сразу, а детям оставить записку.
3Идея
Дерево отрезков с отложенными поправками. В узле — минимум и максимум его дней и записка «прибавить d» для детей. Поправка спускается как запрос: узлу, который целиком внутри, прибавляем d к минимуму, максимуму и записке и вниз не идём; через частично задетый узел проходим, сначала отдав его записку детям, а на обратном пути пересчитываем его минимум и максимум из детей. Вопрос спускается так же, тоже отдавая записки по пути. Обе операции посещают не больше четырёх узлов на уровень — O(log n).
4Разбор
Решение на Go — рекурсивное дерево из статьи, только с одной запиской «прибавить». Записка склеивается сложением: две прибавки подряд — одна прибавка суммы, поэтому порядок здесь неважен.
Решение на Python устроено без рекурсии: на Python рекурсивный спуск в несколько раз медленнее цикла. Листья лежат в ячейках n…2n − 1, родитель ячейки i — ячейка i/2. Поправка обходит отрезок снизу вверх, как запрос дерева снизу вверх, и каждому взятому узлу прибавляет d к минимуму, максимуму и записке d[i]. Потом предки двух крайних листьев пересчитываются: минимум узла — меньший из минимумов детей плюс его собственная записка, ведь записка относится ко всему поддереву. Перед вопросом записки на путях от корня к двум крайним листьям проталкиваются сверху вниз — после этого ответы всех узлов, которые возьмёт вопрос, верны.
4+Решение
5Сложность
Построение — O(n), каждая операция — O(log n), всего O(n + q log n) времени и O(n) памяти. Прямой подход — цикл по дням поправки и срез для вопроса — стоит O(n) на операцию: в четвёртом тесте 50 000 операций по отрезкам длиной в десятки тысяч.
6Типичные ошибки
- Цикл по дням поправки. Верно, но O(n·q): поправки к десятилетиям — это тысячи дней каждая.
- Забыть протолкнуть записку в вопросе. Узел, через который вопрос спускается, должен отдать записку детям, иначе ответы детей устарели. На маленьких тестах это часто незаметно.
- В версии снизу вверх забыть собственную записку узла при пересчёте. Минимум узла — это min(детей) +
d[i], а не просто min(детей): записка ещё не отдана вниз. - 32-битные числа. Значения до 10⁹ и до 50 000 поправок по 10⁹ дают числа порядка 5·10¹³ — седьмой тест это проверяет.