Задача №1364. Сугробы на ЛЭП
Служба электроснабжения проводит мониторинг уровня снега, лежащего на ЛЭП Нью-Васюки - Москва. Вся ЛЭП разбивается на участки опорами. Снег имеет свойства падать на какой-либо интервал ЛЭП, если там уже лежал какой-либо снег, то высота снежного покрова на этом участке суммируется. Также снег имеет тенденцию таять на участке трассы в результате оттепели, при этом известно, что не бывает сугробов отрицательной высоты. Энергетикам крайне важно уметь узнавать суммарную высоту снежного покрова на некоторых последовательных участках, чтобы знать вероятность обрыва проводов.
В первой строке входного файла содержатся два числа: N – (1 ≤ N ≤ 10 000) и M – количество команд (1 ≤ M ≤ 50 000). Каждая команда имеет вид “1 L R S”, что означает, что на участок с L-ой опоры по R-ую опору выпало S сантиметров снега (S может быть и отрицательным, тогда это означает, что такое количества снега растаяло), или “2 L R” – запрос суммарной высоты снега на участке с L-ой опоры по R-ую. Опоры нумеруются от 0 до N. Гарантируется, что для запросов вида “1 L R S” при S < 0 на каждом участке между опорами L и R уровень снега составляет не менее S.
На каждую команду 2 (запрос) вы должны выводить число K – суммарную высоту снежного покрова, лежащего на проводах с L-ой опоры по R-ую. Каждое число должно выводиться на новой строке. Известно, что в процессе работы суммарное количество снега на любом интервале не превышает 231.
10 5 1 0 9 10 1 1 5 -3 2 4 8 1 0 6 25 2 0 2
37 67