F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
Problem 5089. -- 最大连续子段和

5089: 最大连续子段和

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 351  Solved: 169
[Submit][Status][Discuss]

Description

给出一个长度为 n 的序列,要求支持如下两种操作:
A  l  r  x :将 [l,r] 区间内的所有数加上 x ;
Q  l  r : 询问 [l,r] 区间的最大连续子段和。
其中,一个区间的最大连续子段和指的是:该区间所有子区间的区间和中的最大值(本题中子区间包括空区间,区间和为 0 )。

Input

第一行两个整数 n、m,表示序列的长度以及操作的数目。
之后的 m 行,每行输入一个操作,含义如题目所述。保证操作为  A  l  r  x  或  Q  l  r  之一。
对于 30% 的数据,n,m≤300 ;
对于 60% 的数据,n,m≤1000 ;
对于 100% 的数据,1≤n,m≤50000, |a_i |≤〖10〗^9, 1≤x≤40000, 1≤l,r≤n

Output

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

Sample Input

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

Sample Output

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

HINT

Source

By GXZlegend

[Submit][Status][Discuss]

HOME Back