XXXXXXXX - Sum of Distinct Numbers

no tags 

You are given N numbers. You have to perform two kinds of operations:
U x y - x-th number becomes equal to y.
Q x y - calculate the sum of distinct numbers from x-th to y-th. It means that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7).

Input

The first line of input contains an integer N. 1<=N<=50000
The second line consists of N numbers.
The third line consists of an integer Q. 1<=Q<=100000
The following Q lines will consist of queries of the form described in the task description.
All numbers in input will fit in the signed 32-bit type.

Output

Output an answer for every query of the second type.

Example

Input:
5
1 2 4 2 3
3
Q 2 4
U 4 7
Q 2 4

Output:
6
13

Hint: Time limit is ~ 1.5*(my program's execution time in the worst case)


hide comments
hackerbhaiya: 2021-06-24 11:05:54

This can be solved by just simple square root decomposition + prefix sums. No need to use mo's algorithm. My code : <snip>

[NG]: Yes we know you can do square root decomposition, as indicated by your comments in just about every problem on square root decomposition. Also, read the footer.

Last edit: 2021-06-24 12:53:41
prmondal: 2021-05-21 11:50:24

block size n^(2/3) + MO's algorithm with update + compression + long long ans -> AC

oudarja_002: 2020-08-05 13:21:34

Why compression is needed??

polyakoff: 2020-04-19 02:23:33

Unfairly for Java coders!

rootkonda: 2020-03-08 11:21:00

Set the block size to n^(2/3) to avoid TLE If you are using MO's algorithm with update + compression.

Last edit: 2020-03-08 11:21:21
nour_massri: 2019-03-10 10:28:05

MO with update + compression = AC
for those who are getting WA at 20th test case try to use long long

szawinis: 2018-06-30 06:48:46

Seems like segment tree + dynamic segment tree is possible for this problem.

swapnil_007: 2017-12-16 00:18:17

Mo with update + compression....AC

mahmud2690: 2017-11-15 18:16:33

segment trees <3

aviroop123: 2017-08-31 20:25:22

Can this be solved using mo's algorithm using updates?...getting TLE :p


Added by:Sergey Kulik
Date:2011-06-23
Time limit:1s
Source limit:44444B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Known problem