P15147 [SWERC 2024] Titanomachy

双倍经验：

在古希腊神话中，人们相信奥林匹亚众神的力量来源于与泰坦的漫长战争。 最近的一些考古发掘中，一个考古队发现了描述人们想象中这场战争如何发生的手稿。 奥林匹亚众神的领袖宙斯与泰坦的领袖克洛诺斯各自挑选了他们最精锐的 $N$ 名士兵来战斗。 随后，士兵们排列成两行，一行仅包含奥林匹亚众神，另一行包含泰坦，使得每个士兵恰好面对一名对手。 战争开始时，每一对士兵 $i$（$1 \le i \le N$）都有一个分数 $A_i$，这是一个整数，代表战争中哪一方占优势。正数表示宙斯和奥林匹亚众神占优，负数表示泰坦占优。 战争期间发生了 $Q$ 个事件。这些事件有两种类型：要么由于宙斯和克洛诺斯的行动（例如用闪电劈开山峦），所有士兵对的相对实力发生了变化；要么宙斯对他的军队优势进行了战略评估。 在第一种情况下，每个 $A_i$ 都加上同一个整数 $X$。如果 $X$ 大于 $0$，意味着宙斯增强了他的军队实力；负值意味着泰坦增强了实力；$0$ 表示没有变化。 在第二种情况下，宙斯关注一个士兵区间 $[L, R]$（$1 \le L \le R \le N$）：他考虑所有可能的子区间，即所有满足 $L \le l \le r \le R$ 的 $l, r$，并为每个子区间计算和 $A_l + A_{l+1} + \cdots + A_r$。他计算所有这些和中最大的值 $M$，并宣布 $V = \max(M, 0)$ 为其军队优势的战略评估值。 显然，宙斯的智慧使他能够瞬间计算出这些值，但不幸的是，他没有在任何地方记录它们。 你作为语文学家，任务是提供宙斯在战争期间进行的所有战略评估的值。

输入的第一行包含两个空格分隔的整数 $N$ 和 $Q$。第二行包含 $N$ 个空格分隔的整数 $A_i$，表示战争开始时的状态。接下来的 $Q$ 行按时间顺序描述战争事件，每行是以下两种之一： - 单词 **STRENGTH**，后跟一个空格和一个整数 $X$，表示军队的实力发生了变化。 - 单词 **ASSESS**，后跟空格分隔的整数 $L$ 和 $R$，表示宙斯通过关注区间 $[L, R]$（$1 \le L \le R \le N$）对其军队优势进行了战略评估。

对于宙斯每次进行战略评估，按照它们在输入中出现的顺序，输出一行该评估的值 $V$。

#### 数据范围 - $1 \le N \le 3 \times 10^5$ - $1 \le Q \le 3 \times 10^5$ - 对于 $i = 1, \dots, N$，$-10^9 \le A_i \le 10^9$。 - 所有 $X$ 整数在 $-10^9$ 到 $10^9$ 之间（含端点）。 - 在战争的任何时刻，对于所有 $i = 1, \dots, N$，都满足 $-2 \times 10^9 \le A_i \le 2 \times 10^9$。 翻译由 DeepSeek 完成