#1252. GSS3 - Can you answer these queries III
GSS3 - Can you answer these queries III
题目描述
给定一个长度为 的整数序列 。有 个操作,操作共有两种类型:
- 修改序列中的第 个元素。
- 对于给定的区间 ,求 $\max\{A_i + A_{i+1} + \dots + A_j \mid x \le i \le j \le y\}$。
输入格式
第一行包含一个整数 。
第二行包含 个整数,表示序列 。
第三行包含一个整数 。
接下来的 行,每行包含一个操作,格式如下:
0 x y:将 修改为 ()。1 x y:输出 $\max\{A_i + A_{i+1} + \dots + A_j \mid x \le i \le j \le y\}$。
输出格式
对于每个类型为 的询问,根据题目要求输出一个整数。
样例
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
6
4
-3
题目来源:洛谷 SP1716