区间最大子段和

题目描述

Y 同学手中有一个长度为 $N$ 的整数序列 $A = \{a_1, a_2, \ldots, a_N\}$。

为了分析这个序列的局部特性，Y 同学需要对其进行 $M$ 次操作。操作分为两种类型：

1. 单点修改：给定整数 $x$ 和 $y$，将序列中第 $x$ 个位置的元素修改为 $y$，即执行 $a_x \leftarrow y$。
2. 区间查询：给定整数 $x$ 和 $y$（满足 $x \le y$），询问在区间 $[x, y]$ 内，最大的连续子段和是多少。 形式化地，你需要求出：$$\max \{ \sum_{k=i}^{j} a_k \mid x \le i \le j \le y \} $$

请你编写程序帮助 Y 同学完成这些操作。

输入格式

第一行包含一个整数 $N$，表示序列的长度。 第二行包含 $N$ 个整数，表示初始序列 $A = \{a_1, a_2, \ldots, a_N\}$。 第三行包含一个整数 $M$，表示操作的次数。 接下来 $M$ 行，每行包含三个整数 $op, x, y$，描述一个操作：

• 如果 $op = 0$，表示进行单点修改，将 $a_x$ 修改为 $y$。
• 如果 $op = 1$，表示进行区间查询，求区间 $[x, y]$ 内的最大子段和。

输出格式

对于每一个 $op = 1$ 的查询操作，输出一行一个整数，表示该区间内的最大连续子段和。

样例

样例输入 #1

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

样例输出 #1

6
4
-3

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le N \le 50000$
• $1 \le M \le 50000$
• $-10000 \le a_i, y \le 10000$
• 对于 $op=0$，保证 $1 \le x \le N$。
• 对于 $op=1$，保证 $1 \le x \le y \le N$。