Максимум на подотрезках с добавлением на отрезке
Реализуйте эффективную структуру данных для хранения массива и выполнения следующих операций: увеличение всех элементов данного интервала на одно и то же число; поиск максимума на интервале.
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.
Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (m — найти максимум, a — увеличить все элементы на отрезке).
Следом за m вводятся два числа — левая и правая граница интервала.
Следом за a вводятся три числа — левый и правый концы отрезка и число add, на которое нужно увеличить все элементы данного отрезка массива (0 ≤ add ≤ 100000).
Выведите в одну строку через пробел ответы на каждый запрос m.
5 2 4 3 1 5 5 m 1 3 a 2 4 100 m 1 3 a 5 5 10 m 1 5
4 104 104