XXXXXXXX  Sum of Distinct Numbers
You are given N numbers. You have to perform two kinds of operations:
U x y  xth number becomes equal to y.
Q x y  calculate the sum of distinct numbers from xth to yth. 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 32bit 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:
20210624 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>


prmondal:
20210521 11:50:24
block size n^(2/3) + MO's algorithm with update + compression + long long ans > AC 

oudarja_002:
20200805 13:21:34
Why compression is needed??


polyakoff:
20200419 02:23:33
Unfairly for Java coders! 

rootkonda:
20200308 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: 20200308 11:21:21 

nour_massri:
20190310 10:28:05
MO with update + compression = AC


szawinis:
20180630 06:48:46
Seems like segment tree + dynamic segment tree is possible for this problem. 

swapnil_007:
20171216 00:18:17
Mo with update + compression....AC 

mahmud2690:
20171115 18:16:33
segment trees <3 

aviroop123:
20170831 20:25:22
Can this be solved using mo's algorithm using updates?...getting TLE :p 
Added by:  Tooru Ichii 
Date:  20110623 
Time limit:  1s 
Source limit:  44444B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Known problem 