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
Tom Chen:
2009-11-27 13:44:50
Which algorithm can work?
|
|
Alfonso2 Peterssen:
2009-06-26 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: 2011-01-15 06:33:27 |
|
Tony Beta Lambda:
2009-06-25 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: 2011-04-03 13:07:52 |
|
Alfonso2 Peterssen:
2009-06-14 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:
2009-06-10 06:05:29
A simplified version of this problem is QMAX3VN :-) |
Added by: | Alfonso² Peterssen |
Date: | 2009-06-08 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |
Resource: | my own |