#1252. GSS3 - Can you answer these queries III

GSS3 - Can you answer these queries III

题目描述

给定一个长度为 NN 的整数序列 AA。有 MM 个操作,操作共有两种类型:

  1. 修改序列中的第 ii 个元素。
  2. 对于给定的区间 [x,y][x, y],求 $\max\{A_i + A_{i+1} + \dots + A_j \mid x \le i \le j \le y\}$。

输入格式

第一行包含一个整数 NN。

第二行包含 NN 个整数,表示序列 A1,A2,…,ANA_1, A_2, \dots, A_N。

第三行包含一个整数 MM。

接下来的 MM 行,每行包含一个操作,格式如下:

  • 0 x y:将 AxA_x 修改为 yy(∣y∣≤10000|y| \le 10000)。
  • 1 x y:输出 $\max\{A_i + A_{i+1} + \dots + A_j \mid x \le i \le j \le y\}$。

输出格式

对于每个类型为 11 的询问,根据题目要求输出一个整数。

样例

4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
6
4
-3

题目来源:洛谷 SP1716