小猴编程C++ | 数字替换（小猴编程官网）

学习C++从娃娃抓起！记录下在学而思小猴编程学习过程中的题目，记录每一个瞬间。侵权即删，谢谢支持！

附上汇总贴：小猴编程C++ | 汇总-CSDN博客

【题目描述】

小猴有一个包含 n 个整数的数列 A={a1,a2,…,an}，小猴想要对数列 A 做如下操作若干次：

• 给定两个整数 x,y，你需要将数列 A 中所有值等于 x 的元素替换为 y。

现在小猴告诉你，他具体执行了 q 次上述操作。对于第 i 次操作，你需要回答小猴在第 i 次操作之后，数列 A 中的所有元素的总和是多少。

【输入】

第一行，包含一个整数 n。

第二行，包含 n 个整数 a1,a2,…,an。

第三行，包含一个整数 q。

接下来 q 行，每行两个整数 xi,yi，表示第 i 次操作，即将数列 A 中所有值等于 xi 的元素替换为 yi，保证 xi 在数列 A 中一定存在。

【输出】

共 q 行，第 i 行表示第 i 次操作之后数列 A 中的所有元素的总和。

【输入样例】

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

【输出样例】

10
11
13
11
8

【代码详解】

 #include <bits/stdc++.h>
using namespace std;
int n, q, x, y;
int a[200005];
long long cnt[100005]={0}, sum;
int main()
{
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        sum += a[i];
        cnt[a[i]]++;
    }
    cin >> q;
    for (int i=1; i<=q; i++) {
        cin >> x >> y;
        if (x!=y) {
            sum += cnt[x]*(y-x);
            cnt[y] += cnt[x];
            cnt[x] = 0;
        }
        cout << sum << endl;
    }
    return 0;
}

【运行结果】

4
1 2 3 4
5
1 1 
10
1 2
11
3 5
13
4 2
11
2 1
8