Тёплые дни
Архив погоды хранит среднюю температуру за каждый из n дней, в десятых долях градуса. К архиву приходят два вида обращений, вперемешку:
1 l r x— сколько дней с l-го по r-й были не холоднее x, то есть с температурой не меньше x;2 l r d— поправка: выяснилось, что с l-го по r-й день датчик врал, и ко всем этим дням нужно прибавить d.
Ответьте на все обращения первого вида. Четыре теста — настоящий архив: средняя температура Алматы за каждый день 1941–2025 годов по реанализу ERA5. В одном из них для каждого лета спрашивают, сколько дней с июня по август было теплее +25°.
В примере сначала не холоднее 3,5° три дня из шести: 4,0, 5,0 и 6,0. После поправки на +1,0° для дней со второго по четвёртый их становится четыре, а третий день теперь ровно 4,0°.
Вход
В первой строке n и q (1 ≤ n ≤ 50 000, 1 ≤ q ≤ 5000). Во второй — n целых температур. Дальше q строк по четыре целых: тип, l, r (1 ≤ l ≤ r ≤ n) и x или d. Все числа и все температуры после поправок по модулю не больше 109.
Выход
Ответы на обращения первого вида, по одному в строке, в порядке обращений.
Примеры
Пример 1
6 4 10 20 30 40 50 60 1 1 6 35 2 2 4 10 1 1 6 35 1 3 3 40
3 4 1
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Прочитать все дни периода — до 50 000 шагов на обращение, а обращений тысячи. Нужно отвечать за целые куски сразу. Что про кусок нужно знать, чтобы быстро сосчитать в нём дни не холоднее x?
2Подсказка 2
Если значения куска отсортированы, ответ — двоичный поиск. А поправка ко всему куску не меняет порядка: её можно не вносить в каждое значение, а запомнить для куска целиком.
3Идея
Корневая декомпозиция: режем дни на блоки по B ≈ √n. У блока — отсортированная копия его значений и общая добавка. Период [l, r] накрывает несколько блоков целиком и режет не больше двух. Целый блок отвечает двоичным поиском: дней не холоднее x в нём столько, сколько значений копии не меньше x − добавка. В разрезанных блоках смотрим дни по одному. Поправка к целому блоку — одно сложение с добавкой; к разрезанному — поправить его дни и пересортировать копию.
4Разбор
Дерево отрезков здесь не помогает: «сколько значений не меньше x» не складывается из ответов половин, если не хранить в узле отсортированный список, а поправка ко всему отрезку такие списки разрушает. Блоки устроены проще: внутри блока ничего не надо склеивать, а добавка к целому блоку списка не трогает.
Обращение стоит O(B + (n/B) log B): до 2B дней по одному и по двоичному поиску на каждый из n/B блоков. Поправка — O(B log B + n/B). При B = √n на пятидесяти тысячах дней это до 450 дней по одному и около 220 двоичных поисков на обращение вместо 50 000 шагов.
На архиве Алматы ответ на летние вопросы показывает потепление: в 1941–1950 годах дней теплее +25° было в среднем 20 за лето, в 2016–2025 — 33, а летом 2025 года — 53.
4+Решение
5Сложность
O((n + q·√n) log n) времени и O(n) памяти.
6Типичные ошибки
- Забыть пересортировать. После поправки части блока его дни изменились, а отсортированная копия — нет. Пока блок разрезан запросами, ошибка не видна; как только его спросят целиком, двоичный поиск идёт по старым значениям. Это
wrong.py. - Забыть добавку в разрезанном блоке. День разрезанного блока — его значение плюс добавка блока: поправки к блоку целиком могли прийти раньше.
- Отсортировать копию с добавкой. Если вписать добавку в копию, при следующей поправке целого блока её придётся снова вписывать во все значения — и выигрыш пропадёт.