(2055)0x40数据结构进阶（0x43 线段树）例题1：你能回答这些问题吗

SP1716 GSS3 - Can you answer these queries III（改数据输入格式）

【题意】

给定长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：

• $1$ $x$ $y$：查询区间 $[x,y]$ 中的最大连续子段和，即求 $\sum_{i=l}^ra_i(x≤l≤r≤y)$。

• $2$ $x$ $y$：把 $A_x$ 改成 $y$。

对于每个查询指令，输出一个整数表示答案。

【输入格式】

第一行两个整数 $N,M$（$N \le 5\times 10^5,M \le 10^5$)。

第二行 $N$ 个整数 $A_i$。

接下来 $M$ 行每行3个整数 $k,x,y$，$k=1$ 表示查询（此时如果 $x>y$ ，请交换 $x,y$），$k=2$ 表示修改。

【输出格式】

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

【输入样例】

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

【输出样例】

2
-1