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
|
heshuwan:
2023-11-10 15:03:01
I have WA so many times...... |
|
lxy2000:
2022-07-29 07:59:10
fhq-treap |
|
changyouren:
2021-10-07 03:13:53
Treap |
|
likhon5:
2020-09-17 14:54:04
got ac using treap, it took 2.51 s but still ac |
|
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
|
|
krist7599555:
2017-04-23 16:20:23
~200 line of code + optimize ~70 line
|
|
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?
|
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 |