U225384 I_AK_Ynoi的第六分块

问 [nzhtl1477（lxl）](https://www.luogu.com.cn/user/3296)。

[I_AK_Ynoi](https://www.luogu.com.cn/user/742628) 给了你一个长为 $n$ 的序列 $a$，有 $m$ 次操作。 1. 把区间 $[l,r]$ 内所有数都加上 $x$。 2. 查询区间 $[l,r]$ 内的最大子段和，可以不选数。

第一行两个整数 $n,m$。 第二行 $n$ 个整数表示序列 $a$。 后面 $m$ 行： - `1 l r x` ：把区间 $[l,r]$ 内所有数加上 $x$。 - `2 l r` ：查询区间 $[l,r]$ 的最大子段和，**可以不选数。**

对于每个询问，输出一个数表示答案。

对于$100\%$的数据，$1\le n,m\le10^5,1\le|a|\le10^9$。 **保证任意时刻 $|a_i|\leq 2\times 10^9$。** 数据强度：中等，没用 P4118 原数据强 ## 广告 - **加入赏关注** 的 [Ynoi 刷题团](https://www.luogu.com.cn/team/45384) - **支持互关** 的 [I_AK_Ynoi](https://www.luogu.com.cn/user/742628)