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