Replacing

题目描述

你有一个由 $N$ 个正整数组成的序列 $A$：$A_{1}, A_{2}, \cdots, A_{N}$。 你将按顺序执行以下 $Q$ 次操作：

在第 $i$ 次操作中，你把每个值为 $B_{i}$ 的元素替换为 $C_{i}$。

对于每个 $i$ $(1 \leq i \leq Q)$，求 $S_{i}$：第 $i$ 次操作之后序列 $A$ 中所有元素的和。

输入格式

输入按照下列格式由标准输入给出： $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 位整数。

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

11
12
16

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

8
4
4

2
1 2
3
1 100
2 100
100 1000

102
200
2000

提示

输入中的所有数值均为整数。 $1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}$ $B_{i} \neq C_{i}$最初，序列 $A$ 为 $1,2,3,4$。 每次操作之后，它变为如下：

$2, 2, 3, 4$ $2, 2, 4, 4$ $4, 4, 4, 4$
注意序列 $A$ 中可能不存在值为 $B_{i}$ 的元素。

标签: AtCoder|abc171D

来源

AtCoder|abc171D