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
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. 

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


Tom Chen:
20091127 13:44:50
Which algorithm can work?


Alfonso2 Peterssen:
20090626 16:53:11
Fast IO is not needed, anyway, lines ends with "\n\r", I generate the tests using a C++ Windows compiler. Last edit: 20110115 06:33:27 

Tony Beta Lambda:
20090625 13:12:12
It seems that there is some unexpected carriage returns, linefeeds or spaces at end of line, so be careful using getchar()... Last edit: 20110403 13:07:52 

Alfonso2 Peterssen:
20090614 20:14:04
The text says "non empty", and specify "print max{Ai + Ai+1 + .. + Aj  x <= i <= j <= y}.", in case that all the numbers in the query range are negative the answer is the biggest one, not 0. 

[Trichromatic] XilinX:
20090610 06:05:29
A simplified version of this problem is QMAX3VN :) 
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 