线段树模板题
Background
线段树模板题
Description
给定一个长度为n的序列,支持区间加,区间查询最大值。
Input
第一行两个数n,m表示序列长度和操作次数。
下一行n个数表示原始序列A。
下面m行,每行一个opt,
opt=1是区间加操作,接下来三个数L,R,x,表示[L,R]区间加上x;
opt=2是区间查询最大值,接下来两个数L,R表示区间[L,R]。
Output
对于每个询问,输出一行表示答案。
Sample 1
Input
2 2
1 2
1 1 1 3
2 1 2
Output
4
Limitation
1s,512MB
Hint
对于20%的数据,n<=5000,m<=5000;
对于60%的数据,n<=50000,m<=50000;
对于100%的数据,n<=500000,m<=500000。
操作中区间加中的|x|<=1000,原始序列|A[i]|<=1000。