GSS3 - Can you answer these queries III


You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Input

The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Output

For each query, print an integer as the problem required.

Example

Input:
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

Output:
6
4
-3

hide comments
baadshah_: 2016-07-15 16:38:22

AC in one Go same as GSS1 with one update function

iharsh234: 2016-07-09 18:01:56

implement using vector no chances of runtime error then. ^_^

Deepak : 2016-06-18 17:55:48

AC in one go.do GSS1 before this.

Shubham Pandey: 2016-06-02 13:45:49

just the addition of update function to GSS1

Mayank Garg: 2016-05-19 11:12:23

Best question ever solved by me on Segment trees :-)

try2catch: 2016-03-30 02:49:49

Getting grip on segmented tree. Java took 0.2s.

Aditya: 2016-03-22 17:39:59

AC in one go ! just add the update function to GSS1.

minhthai: 2016-02-14 15:46:04

thanks for the time limit that allows java solutions pass :)

Last edit: 2016-02-14 15:47:58
trieuman189: 2015-10-27 20:01:59

Blog Thuật toán SPOJ can help you : http://www.oni.vn/uR57W

carofe82: 2015-10-25 06:09:54

Finally got it done. I learned a lot. A custom Fast Scanner needs to be implemented to be able to pass. There are extra spaces and bad new lines in the test case, and the java Scanner is too slow.


Added by:Bin Jin
Date:2007-08-03
Time limit:0.330s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C++ 5
Resource:own problem