Снежные шапки Тянь-Шаня


Отправить решение Решать в редакторе

Сложность: 95%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Вдоль хребта Кюнгёй Ала-Тоо идут n вершин, на вершине i лежит снежная шапка высотой a[i] сантиметров (бывает и отрицательная «высота» — проталины ниже уровня отсчёта). Гляциологи моделируют погоду четырьмя видами событий:

  • 1 l r x — оттепель: на всех вершинах с l по r снег выше уровня x тает до x, то есть a[i] = min(a[i], x);
  • 2 l r x — снегопад (или ветер): на всех вершинах с l по r высота меняется на x, то есть a[i] = a[i] + x;
  • 3 l r — запрос: суммарная высота a[l] + … + a[r];
  • 4 l r — запрос: наибольшая высота среди a[l], …, a[r].

Рисунок

Обработайте все события.

Входные данные

В первой строке — числа n и q (1 ≤ n, q ≤ 2 · 10⁵). Во второй строке — n чисел a[i] (|a[i]| ≤ 10⁹). В каждой из следующих q строк — событие в описанном формате (1 ≤ l ≤ r ≤ n, в событии 1 |x| ≤ 10⁹, в событии 2 |x| ≤ 10⁴).

Выходные данные

Для каждого запроса 3 и 4 выведите ответ в отдельной строке.

Пример 1

Вход:

5 5
1 5 3 2 4
1 1 5 3
3 1 5
2 2 4 5
4 1 3
3 4 4

Выход:

12
8
7

Пояснение

После оттепели 1 1 5 3 высоты 1 3 3 2 3, сумма 12. После снегопада 2 2 4 5 высоты 1 8 8 7 3, максимум на отрезке 1…3 равен 8.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n, q ≤ 1000, ещё в 15 % тестов нет событий 2.

Подсказка

Segment tree beats: в узле дерева храните максимум, второй максимум (строго меньший) и количество максимумов.


Комментарии

Еще нет ни одного комментария.