Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:256 MB

#681. 最大连续子段和

Statistics

题目描述 给出一个长度为 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 $。