问题 C: 最大子段和问题
内存限制：1024 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：31
解决：13
题目描述
给定一个有 $N$ 个整数的数组 $A$ ，有 $Q$ 次操作
- 1 x d : $A_x$ 修改为 $y$
- 2 l r : 查询 $l$ 到 $r$ 的最大子段和
- 1 x d : $A_x$ 修改为 $y$
- 2 l r : 查询 $l$ 到 $r$ 的最大子段和
输入
第一行两个整数 $1 \le N, Q \le 2 \times 10^5$
第二行 $N$ 个整数 $-10^9 \le A_i \le 10^9$ 个整数 $ 1 \le i \le N$
接下来 $Q$ 行，每行一个形如1 x d或者2 l r的操作，保证 $1 \le x \le N, 1 \le l \le r \le N, -10^9 \le d \le 10^9$ 。
第二行 $N$ 个整数 $-10^9 \le A_i \le 10^9$ 个整数 $ 1 \le i \le N$
接下来 $Q$ 行，每行一个形如1 x d或者2 l r的操作，保证 $1 \le x \le N, 1 \le l \le r \le N, -10^9 \le d \le 10^9$ 。
输出
对于每次操作2输出一个整数代表区间 $[l, r]$ 的最大子段和
样例输入 复制
5 5
-1 2 -3 4 -5
2 4 5
1 2 4
2 1 5
1 4 -1
2 2 4样例输出 复制
4
5
4