CS
Задачник Базовый курс EN

Задача

Первый заморозок

дерево отрезков запросы на отрезке поиск наука и физика олимпиады

Агроном планирует уборку и для каждого года спрашивает одно и то же: когда после 1 августа впервые выдался день со среднесуточной температурой не выше заданного порога — нуля, минус пяти, минус десяти градусов. Ряд при этом не застыл. Когда датчик ломается, испорченный участок ряда заполняют одним значением — нормой для этого сезона, — и такие замены приходят вперемешку с вопросами.

Один из тестов — настоящая среднесуточная температура Алматы с 1 января 1941 года по 31 декабря 2025-го в десятых долях градуса, 31 046 дней. Некоторые пороги в нём холоднее любого дня ряда.

Вход

В первой строке n и q (1 ≤ n ≤ 100 000, 1 ≤ q ≤ 50 000). Во второй — n целых чисел a1, …, an, |ai| ≤ 10⁹. Дальше q строк, в каждой одна операция:

  • = l r x — каждому из чисел al, …, ar присвоить x (1 ≤ l ≤ r ≤ n, |x| ≤ 10⁹);
  • ? l t — найти наименьшее i ≥ l, для которого ai ≤ t (1 ≤ l ≤ n, |t| ≤ 2·10⁹).

Выход

На каждый вопрос — строка с найденным номером i или −1, если такого дня нет.

Примеры

Пример 1

Вход
16 6
-21 -10 -16 -72 -115 -133 -154 -191 -182 -116 -68 -68 -99 -88 -62 -67
? 1 -150
= 5 9 0
? 1 -150
? 3 -100
? 11 -68
? 16 -68
Выход
7
-1
10
11
-1

Пример 2

Вход
1 4
5
? 1 5
? 1 4
= 1 1 -5
? 1 4
Выход
1
-1
1

Ограничения

Время · Python
6000 мс
Время · Go
2000 мс
Память
256 МБ
Проверка
8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Пройти по дням от l, пока не встретится холодный, просто, но если холодного дня нет до самого конца, проход длиной в весь ряд. Что нужно знать о целом куске ряда, чтобы понять, что в нём холодного дня нет?

2Подсказка 2

Минимум. Если минимум куска выше порога, весь кусок можно перепрыгнуть. Дерево отрезков хранит минимум для кусков всех размеров, и поиск может идти по нему сверху, как спуск в статье. Остаётся замена отрезка одним значением.

3Подсказка 3

Замена всех дней узла одним числом x делает минимум узла равным x — детей спрашивать не нужно. Это записка «присвоить x», которую узел отдаёт детям, когда через него проходят.

4Идея

Дерево отрезков с минимумом в узлах и отложенным присвоением. Замена отрезка ложится записками на O(log n) узлов. Вопрос — спуск: узел, который кончается раньше l или чей минимум выше t, пропускаем целиком; иначе, отдав записку детям, ищем сначала в левом ребёнке, потом в правом. Лист, до которого дошли, — ответ.

5Разбор

Решение на Go — рекурсивный спуск из статьи. Почему он быстрый: неудачный заход в узел, где минимум не выше t, но все такие дни левее l, возможен только у узлов, которые содержат l внутри, — их по одному на уровень. Узел, целиком лежащий правее l, с минимумом не выше t, наверняка содержит ответ, и из него спуск идёт одним путём до листа. Итого O(log n) узлов.

Решение на Python устроено без рекурсии и над деревом из 2k листьев: лишние листья — плюс бесконечность, они никогда не холоднее порога. Сначала записки на пути от корня к листу l проталкиваются вниз. Потом поиск идёт по блокам, из которых складывается отрезок [l, конец): от листа l вверх, пока узел — левый ребёнок, затем вправо на соседа. Каждый такой блок — правый сосед узла на пути к l, и записок над ним уже нет. Как только у блока минимум не выше t, спускаемся в него: в левого ребёнка, если там минимум не выше t, иначе в правого, проталкивая записки по дороге.

Замена отрезка — тоже без рекурсии: записки на путях к двум концам проталкиваются сверху вниз, отрезок обходится снизу вверх, взятые узлы получают значение и записку, потом предки двух концов пересчитываются снизу вверх.

5+Решение
6Сложность

Построение — O(n), каждая замена и каждый вопрос — O(log n). Проход по дням стоит O(n) на вопрос, и тесты с порогом холоднее всего ряда превращают его в q·n — миллиарды шагов. Замена срезом в Python быстрая, на C, — медленно именно искать.

7Типичные ошибки
  • Проход по дням от l. На настоящей погоде он часто находит ответ за несколько недель, и кажется быстрым. Но порог холоднее всего ряда или долгая тёплая осень заставляют пройти до конца.
  • Двоичный поиск по ответу с запросом минимума на [l, m]. Правильно, но O(log² n) на вопрос: работает, хотя в несколько раз медленнее спуска.
  • Забыть протолкнуть записку при спуске. Узел с запиской «присвоить» знает свой минимум, а его дети — ещё нет: спуск в детей без проталкивания найдёт старый холодный день, которого уже нет.
  • Нестрогое сравнение. Нужен день не выше порога, ai ≤ t: в первом примере день 11 равен порогу −68 и подходит, а день 16, −67, — нет.

Алгоритмы задачи

DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи
Каталог алгоритмов