区间最大子段和

题目描述

给定一个序列 $a_i$，维护两种操作：

• 1 l r 查询 $\max_{l \le i \le j \le r}\sum_{k=i}^j a_k$，即 $a[l \sim r]$ 的最大子段和。
• 2 p x 将 $a_p \leftarrow x$，即单点修改。

输入格式

第一行包含两个整数 $n, m$，表示给定序列与操作次数。 第二行包含 $n$ 个整数 $a_i$，表示给定序列。 接下来 $m$ 行，每行包含一条指令，如上所述。

数据范围

$n, m \le 2\times 10^5$ $|a_i|,x \le 10^6$

输出格式

对于每次查询，输出一个整数，表示答案，占一行。

样例 #1

样例输入 #1

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 2 3

样例输出 #1

2
-1