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
aayush_b1999:
20190813 00:00:00
solve GSS1 before this 

explodingfrz:
20190704 10:55:40
Very nice test cases , O(nm) brute force passes in 0.31s....


lukamosiashvil:
20190625 12:59:22
you can solve this with sqrt decomposition too. 

syed_tanveer:
20190620 18:05:45
GSS1 + Point update 

akashbhalotia:
20190517 17:44:58
Works for Java.


gabrijel:
20190327 23:35:24
Solved with segment tree and with buckets! Both times AC in 2 goes! 

gabrijel:
20190327 22:46:04
Bin Jin is a genious! Great problem, great name, great solution... 

fabijanb:
20190327 21:47:56
WOOOW, never seen anything like this before, RECOMMEND!!!! 

linkret:
20190327 16:11:43
such wonderful task thank you very much dear problemsetter :3 

sir_akshat:
20190320 18:14:03
AC in one go 
Added by:  Bin Jin 
Date:  20070803 
Time limit:  0.330s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 
Resource:  own problem 