Beauty of sceneries
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 285
Solved: 76
- Description
- GZ has bought a new camera recently, so he is busy taking pictures in campus these days. There is a road with many beautiful scenery spots, which GZ love so much. Specifically, the scenery spots are placed in a straight line, each one with a “beauty value”. Due to limited time, every time GZ go out to take pictures, he will choose a interval [A, B], which means from the Ath scenery spot to the Bth one (both inclusive), then he wants to know what maximum sum of beauty would be, if he choose some consecutive spots from the interval [A, B].
Note that the beauty value of each scenery spot may change. For example: if the grassland of some spot was destroyed, its beauty value will decrease, or if some animals called MM appear at some spot, its beauty value will increase.
- Input
- Just one case.
First line, two integer N, M ,representing the number of scenery spots and numbers of queries respectively. ( 1 <= N <= 500000, 1 <= M <= 100000 )
Next line with N integers, each integer V[i] represent the initial beauty value of spot 1..N respectively. ( -1000 <= V[i] <= 1000)
Next M line, each line with three integer K, A, B; K represent the type of the query.
if K=1 then GZ will choose some consecutive spots from interval [A, B] to take pictures; ( 1 <= A <= B <= N)
or if K=2 then the beauty value of the Ath spot will change to B. (1 <= A <= N, -1000 <= B <= 1000)
- Output
- For each time GZ take pictures, output the maximum beauty value sum he can get in a single line.
- sample input
-
5 3 1 2 -3 4 5 1 2 3 2 2 -1 1 2 3
- sample output
-
2 -1
- hint
- source