GSS6  Can you answer these queries VI
Given a sequence A of N (N <= 100000) integers, you have to apply Q (Q <= 100000) operations:
Insert, delete, replace an element, find the maximum contiguous(non empty) sum in a given interval.
Input
The first line of the input contains an integer N.
The following line contains N integers, representing the starting
sequence A1..AN, (Ai <= 10000).
The third line contains an integer Q. The next Q lines contains the operations in following form:
I x y: insert element y at position x (between x  1 and x).
D x : delete the element at position x.
R x y: replace element at position x with y.
Q x y: print max{Ai + Ai+1 + .. + Aj  x <= i <= j <= y}.
All given positions are valid, and given values are between 10000 and +10000.
The sequence will never be empty.
Output
For each "Q" operation, print an integer(one per line) as described above.
Example
Input:
5
3 4 3 1 6
10
I 6 2
Q 3 5
R 5 4
Q 3 5
D 2
Q 1 5
I 2 10
Q 1 6
R 2 1
Q 1 6
Output:
8
3
6
3
5
hide comments
kejriwal:
20160501 16:48:46
Strange !! long long gives TLE .. int gives AC !! :D :D 

yzy__hehe:
20160501 05:29:00
so easy Last edit: 20160501 05:34:02 

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

Martin:
20150428 17:11:26
C++ 4.3.2 gets TLE, while C++ 4.9 passes... 

Jordan Alexander:
20140204 02:19:36
If you're going to use a Skip List, you're going to need to optimize it so much it isn't even funny, and then you're still going to have to get lucky with the RNG. 

Tank Chen:
20131130 13:58:37
Those who got WA pay attention to this case:


昌(尼莫):
20130608 07:23:25
I am getting WA constantly ,my program runs upto 10 test cases and fails. So if there are any special cases please help . 

Fotile:
20130509 03:44:10
my CAML program got TLE.:( 

Zhouxing Shi:
20130423 10:21:07
The time limit is too strict. For the largest input data, my program solve out in about 1600ms, but got TLE on SPOJ. 

Ehor Nechiporenko:
20100915 08:29:30
Is it required to make Selfbalancing trees? Or problem can be resolved with using prime search trees?

Added by:  Alfonso2 Peterssen 
Date:  20090608 
Time limit:  0.298s0.447s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JS 
Resource:  my own 