GSS8 - Can you answer these queries VIII
You are given sequence A[0], A[1]...A[N - 1]. (0 <= A[i] < 2^32)
You are to perform Q operations:
- I pos val, insert number val in sequence before element with index pos. (0 <= val < 2^32, if pos = current_length then you should add number to the end of the sequence)
- D pos, delete element with index pos from sequence.
- R pos val, replace element with idex pos by val. (0 <= val < 2^32)
- Q l r k, answer Σ A[i] * (i - l + 1)^k modulo 2^32, for l <= i <= r. (0 <= k <= 10)
Input
The first line of the input contains an integer N (1 <= N <= 100000).
The following line contains N integers, representing the starting sequence A[0]...A[N-1].
The third line contains an integer Q (0 <= Q <= 100000).
Next Q lines contains the queries in given format.
Output
For each "Q" operation, print an integer (one per line) as described above.
Example
Input: 4 1 2 3 5 7 Q 0 2 0 I 3 4 Q 2 4 1 D 0 Q 0 3 1 R 1 2 Q 0 1 0 Output: 6 26 40 4
hide comments
DK...:
2019-11-25 04:49:09
I got Ac in O(k^2*log(n)) per query and using scanf. Nice problem! |
|
mahdibuet3:
2019-11-13 13:15:42
treap does its duty❤ |
|
longxiaokong:
2019-10-22 04:10:28
what is the range of N? |
|
[Rampage] Blue.Mary:
2016-02-19 04:34:54
@chalarangleo: O(n) per query will surely lead to TLE. This problem requires O(logn) per query with (a little bit small constant). |
|
Scape:
2015-10-05 16:14:48
A very nice problem! |
|
chalarangelo:
2015-07-19 21:20:37
I'm getting TLE after 27 cases... It works just fine though for any case I can try (even big input), any comments from OP would be appreciated!
|
Added by: | Evgeny Savinov |
Date: | 2014-04-14 |
Time limit: | 1.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem |