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 ith 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
minhthai:
20160214 15:46:04
thanks for the time limit that allows java solutions pass :) Last edit: 20160214 15:47:58 

trieuman189:
20151027 20:01:59
Blog Thuật toán SPOJ can help you : http://www.oni.vn/uR57W 

carofe82:
20151025 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. 

sujit yadav:
20151022 00:49:08
same as gss1 bt have to add an extra "update" function .... 

carofe82:
20151019 01:46:08
I'm struggling with the IO in this problem.


Habibur Rahman Habib:
20150915 20:43:13
If the statement is "max{Ai, Ai+1 , .., Aj  x<=i<=j<=y }" . Please clear me someone. Thanks in Advances. 

gandalf_:
20150902 10:15:46
YOU SHALL NOT PASS


jas.py:
20150825 12:01:59
there is some issue with spoj,,my same code got SIGSEGV#0 when submitted with C but passed with C++14 Last edit: 20150825 12:02:28 

shiva:
20150805 15:10:37
Why wrong answer #0? Please help. 

Abdullah mohammad fakhri alattar:
20150803 00:59:42
What is wrong answer #0

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