A22931. 替换
填空题
较难
知识点
题目描述
替换
题目描述
有一个包含 N 个正整数 A1, A2, ..., AN 的数列 A 。接下来将进行 Q 次操作：
在第 i 次操作中，将数列中所有值为 Bi 的元素替换为 Ci 。
请针对每次操作（ 1 <=i <=Q ），输出操作后数列 A 的所有元素之和 Si 。
输入格式
第一行，一个整数 N ；
第二行，N 个整数 A1, A2, ..., AN ；
第三行，一个整数 Q 。
接下来 Q 行，每行两个整数 Bi , Ci 。
输出格式
输出 Q 行，每行一个整数 Si ，表示每次操作后的数列总和。
注意：Si 可能超出 32 位整数范围。
输入样例#1
4
1 2 3 4
3
1 2
2 4
3 4输出样例#1
11
15
16输入样例#2
5
1 2 3 4 5
5
1 2
2 3
3 4
4 5
5 1输出样例#2
16
18
21
25
5参考答案
#include <iostream>
#include <cstdio>
using LL = long long;
const int MAX_SIZE = 500000;
LL a[MAX_SIZE];
LL sum = 0;
int main() {
LL n;
std::cin >> n;
for (LL i = 0; i < n; i++) {
LL k;
std::cin >> k;
sum += k;
a[k]++;
}
LL q;
std::cin >> q;
for (LL i = 0; i < q; i++) {
LL b, c;
std::cin >> b >> c;
LL x = a[b];
sum = sum - x * b + x * c;
a[b] = 0;
a[c] = a[c] + x;
std::cout << sum << '\n';
}
return 0;
}
上一题
下一题