P1012浮光掠影（sunset）

【题目背景】

落日余晖映红了特西荼亚海的海面，那是拉德鲁斯大陆上最为广阔的海。

【题目描述】

由于特西荼亚海实在太过巨大，洒落在其上的落日光辉可以被大致分入 $n$ 个亮度不尽相同的区域。由于 Gioush 大队中流传着特西荼亚海掌管着命运的传说，于是大预言家 tfbz 派出了一位观测者来到特西荼亚海旁驻扎，观测特西荼亚海面被光映照的数据。

为了具象化特西荼亚海对命运的影响，tfbz 首先确立了亮度的测量方案，于是通过 tfbz 的仪器，最初每一块区域的亮度分别为 $w_i$。同时 tfbz 认为，亮度和最大的连续区域昭示着将来的命运，若能确切地得到亮度和最大的连续区域的亮度之和，他便可利用此数据，占卜出整个拉德鲁斯大陆在 $1$ 年内的命运。具体地，在一次测量中，观测者需要找到一个区间 $[l,r]$，使得 $\sum_{i=l}^r w_i$ 最大。

不幸的是，特西荼亚海太过神奇，每一天都可能有区域发生亮度的变化，具体地，在观测者驻扎的这段时间内，按顺序一共发生了 $m$ 个以下两种事件之一的事件：

• M p c，第 $p$ 处区域的光辉从原本的值变为了 $c$。
• Q l r，观测者进行了一次测量，得到了只考虑 $[l,r]$ 区间所有区域的情况下，亮度之和的最大值。

现在，观测者返回了 Gioush 大队主营地，tfbz 要从其手中获取到他测量到的所有亮度之和的数据了，可是观测者根本就没有算出来，于是他找到你，给出了初始亮度数据和亮度变化，他希望你能帮他给出确切的亮度之和。

【输入格式】

从文件 $\textbf{\textit{sunset.in}}$ 中读入数据。

第一行两个正整数 $n,m$，分别表示区域数和事件数。

第二行 $n$ 个整数 $w_1,w_2,\cdots,w_n$，表示各区域的初始亮度。

接下来 $m$ 行，每行描述一个事件，格式为 M p c 或 Q l r，含义同题目描述。

【输出格式】

输出到文件 $\textbf{\textit{sunset.out}}$ 中。

对于每个 Q 事件输出一行一个整数，表示只考虑对应区间所有区域的情况下，亮度之和的最大值。

特别地，所选择的连续区间不能为空。

【样例 1 输入】

15 62-2 3 -1 4 -53Q 1 54Q 1 15M 2 -66Q 1 37M 3 108Q 1 4

【样例 1 输出】

162-23-1414

【说明/提示】

【样例 1 解释】

第一次询问中，选择区间 $[2,4]$，亮度和为 $3+(-1)+4=6$。

第二次询问中只能选择 $[1,1]$。由于所选子区间必须非空，答案为 $-2$。

【样例 2】

见选手目录下的 $\textbf{\textit{sunset/sunset2.in}}$ 和 $\textbf{\textit{sunset/sunset2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{sunset/sunset3.in}}$ 和 $\textbf{\textit{sunset/sunset3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{sunset/sunset4.in}}$ 和 $\textbf{\textit{sunset/sunset4.ans}}$。

该组样例符合测试点 $9\sim 16$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{sunset/sunset5.in}}$ 和 $\textbf{\textit{sunset/sunset5.ans}}$。

该组样例符合测试点 $17\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 2\times 10^5$，$-10^9\leq w_i,c\leq 10^9$，$1\leq p\leq n$，$1\leq l\leq r\leq n$。

特殊性质 A：初始状态以及每次修改完成后，均满足 $w_i\geq 0$。

特殊性质 B：初始状态以及每次修改完成后，满足 $w_i<0$ 的位置不超过 $20$ 个。