数据结构题2
Description
【背景】此题又来自洛谷搬运(数据不是)
【题意】
给珂朵莉一个长为n的序列a，支持以下两个操作：
1 x : 把序列所有数都加上x
2 l r : 查询区间[l,r]的区间最大子段和
【输入格式】
第一行两个正整数n，m
第二行n个整数表示a[i]
之后m行每行一个操作
1 x : 把序列所有数都加上x
2 l r : 查询区间[l,r]的区间最大子段和(可以不选数，此时最大子段和是0)
【输出格式】
对于每次询问，输出一行一个数表示答案
【输入样例】
5 7
-10 -3 -2 -4 -5
2 2 4
1 5
2 2 4
1 3
2 1 5
1 2
2 3 5
【输出样例】
0
6
18
19
【提示】
1<=n<=100000
1<=m<=200000
-2000000000<=a[i],x<=2000000000