GSS6 - Can you answer these queries VI

no tags 

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: 2016-05-01 16:48:46

Strange !! long long gives TLE .. int gives AC !! :D :D

yzy__hehe: 2016-05-01 05:29:00

so easy

Last edit: 2016-05-01 05:34:02
trieuman189: 2015-10-27 20:01:55

Blog Thuật toán SPOJ can help you : http://www.oni.vn/uR57W

Martin: 2015-04-28 17:11:26

C++ 4.3.2 gets TLE, while C++ 4.9 passes...

Jordan Alexander: 2014-02-04 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: 2013-11-30 13:58:37

Those who got WA pay attention to this case:
5
1 1 -3 -4 1
1
Q 3 4
ans is -3 not 0

昌(尼莫): 2013-06-08 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: 2013-05-09 03:44:10

my CAML program got TLE.:(

Zhouxing Shi: 2013-04-23 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: 2010-09-15 08:29:30

Is it required to make Self-balancing trees? Or problem can be resolved with using prime search trees?

RE: Test data was made to prevent the use of non-balanced trees, but if you can beat the tests with some cleverness, then you deserve the AC.

Last edit: 2011-01-15 06:44:37

Added by:Alfonso2 Peterssen
Date:2009-06-08
Time limit:0.298s-0.447s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS
Resource:my own