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

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

hide comments
2016-06-02 13:45:49 Shubham Pandey
just the addition of update function to GSS1
2016-05-19 11:12:23 Mayank Garg
Best question ever solved by me on Segment trees :-)
2016-03-30 02:49:49
Getting grip on segmented tree. Java took 0.2s.
2016-03-22 17:39:59 Aditya
AC in one go ! just add the update function to GSS1.
2016-02-14 15:46:04 minhthai
thanks for the time limit that allows java solutions pass :)

Last edit: 2016-02-14 15:47:58
2015-10-27 20:01:59
Blog Thuật toán SPOJ can help you : http://www.oni.vn/uR57W
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.
2015-10-22 00:49:08 sujit yadav
same as gss1 bt have to add an extra "update" function ....
2015-10-19 01:46:08
I'm struggling with the IO in this problem.
I generate a random input of 50,000 integers from -10,000 to 10,000 and then I do 50,000 random operations with random numbers and positions and ranges. I'm testing this with the limits and my code, without the IO part finishes all that on average in 130ms. That gives a lot of room for the IO part. However, I'm getting TLE!
I tried BufferedReader and BufferedWriter to flush everything at the end. Also, I tried the Scanner. I suspect that part of the problem may be the formatting of the test case, my IO operations may be hanging waiting for inputs somewhere. I wish the author (or somebody from SPOJ) fixes the formatting to the test cases of this problem.
Anybody here with the same problem? Any advise?

Last edit: 2015-10-19 01:48:47
2015-09-15 20:43:13 Habibur Rahman Habib
If the statement is "max{Ai, Ai+1 , .., Aj | x<=i<=j<=y }" . Please clear me someone. Thanks in Advances.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.