#6265. 最大连续子段和

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: GXZlegend

题目描述

给出一个长度为 n 的序列,要求支持如下两种操作:

  • A\ \ l\ \ r\ \ x :将 [l,r] 区间内的所有数加上 x

  • Q\ \ l\ \ r : 求 [l,r] 区间的最大连续子段和。

其中,一个区间的最大连续子段和指的是:该区间所有子区间的区间和中的最大值(本题中子区间包括空区间,区间和为 0 )。

输入格式

第一行两个整数 n m ,表示序列的长度以及操作的数目。
第二行 n 个整数,第 i 个整数 a_i 表示序列中的第 i 个数。
之后的 m 行,每行输入一个操作,含义如题目所述。保证操作为 \ A\ \ l\ \ r\ \ x\ \ Q\ \ l\ \ r\ 之一。

输出格式

对于每个 Q 操作输出一行一个整数,表示询问区间的最大连续子段和。

样例

样例输入

5 5
2 -3 0 4 -7
Q 1 2
Q 1 5
A 2 3 2
Q 2 5
Q 1 3

样例输出

2
4
6
3

样例解释

第一、二个 Q 操作时序列为 2,-3,0,4,-7 [1,2] 的最大连续子段和为 [1,1] 的区间和 2 [1,5] 的最大连续子段和为 [4,4] 的区间和 4
第三、四个 Q 操作时序列为 2,-1,2,4,-7 [2,5] 的最大连续子段和为 [3,4] 的区间和 6 [1,3] 的最大连续子段和为 [1,3] 的区间和 3

数据范围与提示

对于 30\% 的数据, n,m\le 300
对于 60\% 的数据, n,m\le 1000
对于 100\% 的数据, 1\le n,m\le 50000,\ |a_i|\le 10^9,\ 1\le x\le 40000,\ 1\le l,r\le n