AtCoder Beginner Contest 171 D - Replacing

D - Replacing

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 400400 points

Problem Statement

You have a sequence AA composed of NN positive integers: A1,A2,⋯,ANA1,A2,⋯,AN.

You will now successively do the following QQ operations:

• In the ii-th operation, you replace every element whose value is BiBi with CiCi.

For each ii (1≤i≤Q)(1≤i≤Q), find SiSi: the sum of all elements in AA just after the ii-th operation.

Constraints

• All values in input are integers.
• 1≤N,Q,Ai,Bi,Ci≤1051≤N,Q,Ai,Bi,Ci≤105
• Bi≠CiBi≠Ci

Input

Input is given from Standard Input in the following format:

NN
A1A1 A2A2 ⋯⋯ ANAN
QQ
B1B1 C1C1
B2B2 C2C2
⋮⋮
BQBQ CQCQ

Output

Print QQ integers SiSi to Standard Output in the following format:

S1S1
S2S2
⋮⋮
SQSQ

Note that SiSi may not fit into a 3232-bit integer.

Sample Input 1 Copy

Copy

4
1 2 3 4
3
1 2
3 4
2 4

Sample Output 1 Copy

Copy

11
12
16

Initially, the sequence AA is 1,2,3,41,2,3,4.

After each operation, it becomes the following:

• 2,2,3,42,2,3,4
• 2,2,4,42,2,4,4
• 4,4,4,44,4,4,4

Sample Input 2 Copy

Copy

4
1 1 1 1
3
1 2
2 1
3 5

Sample Output 2 Copy

Copy

8
4
4

Note that the sequence AA may not contain an element whose value is BiBi.

Sample Input 3 Copy

Copy

2
1 2
3
1 100
2 100
100 1000

Sample Output 3 Copy

Copy

102
200
2000

题意：输入一个n，然后输入n个数字，再输入一个Q，接下来Q行每行输入一个B和C，然后将数组中所有的B换成C，然后把新数组的和输出
题解：开一个数组b，用来储存数组元素中出现的次数，我们在输入数组的元素的时候，先用sum把每个元素加起来，然后数组b中a【i】元素出现的次数++(这样能让我们在后面O(1)的时间算出新数组的总和)
每次B,C输入的时候其实直接用公式sum=sum-(C-B)*b[B];求出sum，然后将数组b更新一下。
代码如下：

#include
#include
#define maxn 100005
#define ll long long 
using namespace std;
ll n,q,a[maxn],sum;
int tm[maxn];
int main(void)
{
    while(~scanf("%lld",&n))
    {
        sum=0;
        for(int i=0;i