/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
あなたは、N 個の正整数 A_{1}, A_{2}, \cdots, A_{N} からなる数列 A を持っています。
あなたは、これから以下の操作を Q 回、続けて行います。
- i 回目の操作では、値が B_{i} である要素すべてを C_{i} に置き換えます。
すべての i (1 \leq i \leq Q) に対して、i 回目の操作が行われた後の数列 A のすべての要素の和、S_{i} を求めてください。
制約
- 入力は全て整数
- 1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}
- B_{i} \neq C_{i}
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}
出力
Q 個の整数 S_{i} を以下の形式で標準出力に出力せよ。
S_{1}
S_{2}
\vdots
S_{Q}
S_{i} は 32 ビット整数に収まらない可能性があることに注意せよ。
入力例 1
4 1 2 3 4 3 1 2 3 4 2 4
出力例 1
11 12 16
はじめ、数列 A は 1,2,3,4 です。
各操作後、 数列 A は以下のようになります。
- 2, 2, 3, 4
- 2, 2, 4, 4
- 4, 4, 4, 4
入力例 2
4 1 1 1 1 3 1 2 2 1 3 5
出力例 2
8 4 4
数列 A に 要素の値が B_{i} であるものが 1 つも含まれていない可能性もあることに注意してください。
入力例 3
2 1 2 3 1 100 2 100 100 1000
出力例 3
102 200 2000
Score : 400 points
Problem Statement
You have a sequence A composed of N positive integers: A_{1}, A_{2}, \cdots, A_{N}.
You will now successively do the following Q operations:
- In the i-th operation, you replace every element whose value is B_{i} with C_{i}.
For each i (1 \leq i \leq Q), find S_{i}: the sum of all elements in A just after the i-th operation.
Constraints
- All values in input are integers.
- 1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}
- B_{i} \neq C_{i}
Input
Input is given from Standard Input in the following format:
N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}
Output
Print Q integers S_{i} to Standard Output in the following format:
S_{1}
S_{2}
\vdots
S_{Q}
Note that S_{i} may not fit into a 32-bit integer.
Sample Input 1
4 1 2 3 4 3 1 2 3 4 2 4
Sample Output 1
11 12 16
Initially, the sequence A is 1,2,3,4.
After each operation, it becomes the following:
- 2, 2, 3, 4
- 2, 2, 4, 4
- 4, 4, 4, 4
Sample Input 2
4 1 1 1 1 3 1 2 2 1 3 5
Sample Output 2
8 4 4
Note that the sequence A may not contain an element whose value is B_{i}.
Sample Input 3
2 1 2 3 1 100 2 100 100 1000
Sample Output 3
102 200 2000