EI 的第六分块

他说他解决了经典根号复杂度问题，怕引起轰动所以撤回了.jpg 不过 [EntropyIncreaser](https://www.luogu.com.cn/user/21423) 确实得到了此题更优的做法。

给定一个整数序列 $a$，支持两种操作： - `1 l r x` 表示给区间 $[l,r]$ 中每个数加上 $x$ - `2 l r` 表示查询区间 $[l,r]$ 的最大子段和（可以为空）

第一行两个正整数 $n,q$，表示序列长度和操作个数。 接下来一行 $n$ 个整数，表示初始的序列 $a$。 接着有 $q$ 行，每行若干个整数，表示一次操作。

对于每个 $2$ 操作，输出一行一个整数表示答案。

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

0
3
2

【数据范围】 对于 $20\%$ 的数据，$1\le n,q \le 1000$； 对于 $60\%$ 的数据，$1\le n,q \le 10^5$； 对于 $100\%$ 的数据，$1\le n,q \le 4\times 10^5$，$|a_i| \le 10^9$，$1 \le x \le 10^6$。 Idea：nzhtl1477 Solution：EntropyIncreaser Code：EntropyIncreaser Data：NaCly_Fish ### 请注意常数优化。