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.


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.


For each "Q" operation, print an integer(one per line) as described above.


3 -4 3 -1 6
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


hide comments
pratham_1: 2019-06-23 12:14:12

Who else tried Treaps ?

DK...: 2019-03-17 06:00:57

Using splay tree i got Ac in 1.17 s using scanf/printf and 1.47 s with fast I/O methods.

dp_1: 2017-07-17 20:29:51

0.55s with avl in c++, no fast I/O needed
0.37s with fast I/O btw

Last edit: 2017-07-17 20:51:16
krist7599555: 2017-04-23 16:20:23

~200 line of code + optimize ~70 line
and half day for many stupid bug :P
if you need your code faster
1.) fast input output
2.) build tree in O(n) !!!

Last edit: 2017-04-24 08:14:52
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.

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
Tom Chen: 2009-11-27 13:44:50

Which algorithm can work?
Is Block-Array faster enough to pass?it take O(sqrt(N)*Q) time...

RE: A O(lg n) per query is expected, but the time limit is quite relaxed...

Last edit: 2010-08-03 19:17:04
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.

Added by:Alfonso² Peterssen
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:my own