AtCoder Beginner Contest 171 D

D - Replacing

---

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $400400$ points

Problem Statement

You have a sequence $\mathrm{AA}$ composed of $\mathrm{NN}$ positive integers: ${\mathrm{A1,A2,\cdots ,ANA1,A2,\cdots ,AN}}^{}$.

You will now successively do the following $\mathrm{QQ}$ operations:

• In the $\mathrm{ii}$-th operation, you replace every element whose value is ${\mathrm{BiBi}}^{}$ with ${\mathrm{CiCi}}^{}$.

For each $\mathrm{ii}$ $(1\le i\le Q)(1\le i\le Q)$, find ${\mathrm{SiSi}}^{}$: the sum of all elements in $\mathrm{AA}$ just after the $\mathrm{ii}$-th operation.

Constraints

• All values in input are integers.
• $\mathrm{1\le N,Q,Ai,Bi,Ci\le 1051\le N,Q,Ai,Bi,Ci\le 105}$
• ${\mathrm{Bi\ne CiBi\ne Ci}}^{}$

---

Input

Input is given from Standard Input in the following format:

$\mathrm{NN}$
${\mathrm{A1A1}}^{}$ ${\mathrm{A2A2}}^{}$ $\cdots \cdots$ ${\mathrm{ANAN}}^{}$
$\mathrm{QQ}$
${\mathrm{B1B1}}^{}$ ${\mathrm{C1C1}}^{}$
${\mathrm{B2B2}}^{}$ ${\mathrm{C2C2}}^{}$
$⋮⋮$
${\mathrm{BQBQ}}^{}$ ${\mathrm{CQCQ}}^{}$

Output

Print $\mathrm{QQ}$ integers ${\mathrm{SiSi}}^{}$ to Standard Output in the following format:

${\mathrm{S1S1}}^{}$
${\mathrm{S2S2}}^{}$
$⋮⋮$
${\mathrm{SQSQ}}^{}$

Note that ${\mathrm{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 $\mathrm{AA}$ is $\mathrm{1,2,3,41,2,3,4}$.

After each operation, it becomes the following:

• $\mathrm{2,2,3,42,2,3,4}$
• $\mathrm{2,2,4,42,2,4,4}$
• $\mathrm{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 $\mathrm{AA}$ may not contain an element whose value is ${\mathrm{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<cstdio>
#include<iostream>
#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<n;++i)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];//求和
            tm[a[i]]++;//a[i]出现的次数自增
        }
        scanf("%lld",&q);
        ll b,c;
        for(int i=0;i<q;++i)
        {
            scanf("%lld %lld",&b,&c);
            sum+=(c-b)*tm[b];
            tm[c]+=tm[b];//更新tm[c]
            tm[b]=0;//更新tm[b]
            printf("%lld
",sum);
        }
    }
    return 0;
}