Снежные шапки Тянь-Шаня
Вдоль хребта Кюнгёй Ала-Тоо идут 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: в узле дерева храните максимум, второй максимум (строго меньший) и количество максимумов.
Комментарии