题目描述
给定长度为 n 的序列 a,维护 q 次操作:
1 p v:把 ap 修改为 v;
2 l r:询问 al,al+1,⋯,ar 的最大子段和(子段必须非空)。
输入格式
第一行两个整数 n,q。
第二行 n 个整数 ai。
接下来 q 行,每行一个操作。
输出格式
对每个 2 操作输出一行一个整数,表示该区间的最大子段和。
样例 #1
样例输入 #1
5 3
-2 1 -3 4 -1
2 1 5
1 3 5
2 1 5
样例输出 #1
4
10
数据规模与约定
| 数据范围 |
说明 |
| 1≤n,q≤105 |
序列长度与操作数 |
| −1000≤ai,v≤1000 |
元素与修改值 |
- 每个结点维护 sum、lmax、rmax、mx 四个量,合并时 mx=max(lmxa,mxb,rmaxa+lmaxb)。