XXXXXXXX - Sum of Distinct Numbers

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)


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

hide comments
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
2021-05-21 11:50:24
block size n^(2/3) + MO's algorithm with update + compression + long long ans -> AC
2020-08-05 13:21:34
Why compression is needed??
2020-04-19 02:23:33
Unfairly for Java coders!
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
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
2018-06-30 06:48:46
Seems like segment tree + dynamic segment tree is possible for this problem.
2017-12-16 00:18:17
Mo with update + compression....AC
2017-11-15 18:16:33
segment trees <3
2017-08-31 20:25:22
Can this be solved using mo's algorithm using updates?...getting TLE :p
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.