AT_abc171_d [ABC171D] Replacing

题目描述

你有一个由 $N$ 个正整数组成的数列 $A = (A_1, A_2, \cdots, A_N)$。

接下来你要连续进行 $Q$ 次如下操作：

• 第 $i$ 次操作时，将所有值为 $B_i$ 的元素替换为 $C_i$。

对于每一次操作 $i$（$1 \leq i \leq Q$），请你求出操作后数列 $A$ 所有元素的和 $S_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

输入 #1

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

输出 #1

11
12
16

输入输出样例 #2

输入 #2

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

输出 #2

8
4
4

输入输出样例 #3

输入 #3

2
1 2
3
1 100
2 100
100 1000

输出 #3

102
200
2000

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N, Q, A_i, B_i, C_i \leq 10^5$
• $B_i \neq C_i$

样例解释 1

初始时，数列 $A$ 为 $1, 2, 3, 4$。每次操作后，数列 $A$ 变为如下：

• $2, 2, 3, 4$
• $2, 2, 4, 4$
• $4, 4, 4, 4$

样例解释 2

请注意，数列 $A$ 中可能不存在值为 $B_i$ 的元素。

由 ChatGPT 4.1 翻译