该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

区间最大子段和

题目背景

交易员小 R 每天记录一条“势能曲线”：曲线被分成 $n$ 段，第 $i$ 段有一个整数数值 $a_i$（可以为负）。她想随时知道：从第 $l$ 段到第 $r$ 段之间，连续若干段（至少一段）的和最大是多少。这条曲线还会被成段地整体修正，于是她想请你写一个能边修改边询问的程序。

题目描述

给定长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。子段指数列中的一段连续位置 $a_l, a_{l+1}, \dots, a_r$（$l \le r$），它的和为 $\sum_{i=l}^{r} a_i$。

接下来有 $q$ 次操作，操作有两种：

• 1 l r x：把 $a_l, a_{l+1}, \dots, a_r$ 中的每一个数都加上 $x$（$x$ 可以为负数）；
• 2 l r：询问子段 $a_l, a_{l+1}, \dots, a_r$ 中非空连续子段和的最大值。

请依次处理这 $q$ 次操作，对每次 2 操作输出答案。

输入格式

从标准输入读入数据。

第一行两个整数 $n, q$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $q$ 行，每行表示一次操作：若是 1 l r x 则共 $4$ 个整数，若是 2 l r 则共 $3$ 个整数。

输出格式

输出到标准输出。

对每次 2 操作输出一行一个整数，表示该次询问的答案。

样例 1 输入

5 3
1 -2 3 -1 2
2 1 5
1 2 3 -10
2 1 5

样例 1 输出

4
2

样例 1 解释

初始序列 $1,-2,3,-1,2$ 中，最优子段是 $3,-1,2$，和为 $4$。接着把 $a_2,a_3$ 各减去 $10$，序列变成 $1,-12,-7,-1,2$，此时最优子段只取最后一个数，答案是 $2$。

样例 2 输入

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

样例 2 输出

0

样例 2 解释

整段减去 $5$ 之后三个数都变成 $0$，最优子段是其中的一个数（或任意一段），答案是 $0$。

特殊性质

• 特殊性质 A：任何时刻都有 $a_i \ge 0$（初始序列非负，并且保证所有操作 1 给出的 $x$ 也非负）。此时“最大子段和”就等于“区间和”，只需要用树状数组（或差分）维护区间加、区间和。
• 特殊性质 B：没有任何操作 1（只做询问，不做修改）。此时序列始终不变，可以先用一次 $O(n)$ 或 $O(n\log n)$ 的预处理，再快速回答区间询问。

数据范围与子任务

| 子任务 | 测试点 | 分值 | $n, q \le$ | $|a_i|, |x| \le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:|:-:| | 1 | $1 \sim 4$ | $20$ | $2000$ | $10^9$ | 无 | | 2 | $5 \sim 8$ | $20$ | $10^5$ | $10^3$ | A | | 3 | $9 \sim 12$ | $20$ | $10^5$ | $10^9$ | B | | 4 | $13 \sim 20$ | $40$ | $10^5$ | $10^9$ | 无额外保证 |

对全部测试数据，保证 $1 \le n, q \le 10^5$，$|a_i| \le 10^9$，$|x| \le 10^9$，$1 \le l \le r \le n$。

部分分提示

• 子任务 1：$n, q \le 2000$，每次询问直接 $O(n)$ 扫描区间求最大子段和（Kadane），操作 1 直接逐格修改，即可拿到 $20$ 分。
• 子任务 2：所有数始终非负，答案就是区间和，用树状数组或差分数组维护区间加即可。
• 子任务 3：没有修改，序列固定，可以用线段树/ST 表这类结构一次性预处理。
• 子任务 4：需要在线段树里同时维护区间和、前缀最大值、后缀最大值与最大子段和，并给结点打上“整体加 $x$”的懒标记。注意：对被完全覆盖的结点整体加 $x$ 时，四个值都要加上 $x \times$ 区间长度；下推懒标记时不要破坏顺序。
• 答案可能很大（绝对值可达 $10^{14}$），请使用 $64$ 位整数。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。