自动搬运

查看原文

来自洛谷，原作者为

	Eason_cyx Play like you never did before?

搬运于2025-08-24 22:48:36，当前版本为作者最后更新于2023-10-03 15:35:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出了这题的数据，就来写篇题解。

不算太难。

$\large\texttt{Part 1:42 pts}$

直接模拟，没什么好说的。

时间复杂度 $O(qn)$，可以通过前两个 $\text{Subtask}$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[300005];
signed main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
	int n,Q; cin >> n;
	long long sum = 0;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	cin >> Q;
	while(Q--) {
		string opt; cin >> opt;
		if(opt == "INFLATION") {
			int x; cin >> x;
			int ans = 0;
    		for(int i = 1;i <= n;i++) {
    		    a[i] += x;
    		    ans += a[i];
    		}
    		cout << ans << endl;
		}
		else {
			int x,y; cin >> x >> y;
			int ans = 0;
			for(int i = 1;i <= n;i++) {
			    if(a[i] == x) a[i] = y;
			    ans += a[i];
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Record

$\large\texttt{Part 2:19 pts}$

本部分讲解如何通过子任务 $3$。

可以发现，要求输出的只是所有价格的总和，而且 $x$ 是一个固定的值。

每一个元素增加 $x$，那么 $n$ 个元素不就增加了 $n \times x$ 吗？

再加上初始的元素和，可以做到 INFLATION 操作时间复杂度 $O(1)$。

于是总时间复杂度降至 $O(q)$，可以通过。

可以尝试将操作离线下来，和前面的 $42$ 分结合，得到 $61$ 分，但是比较麻烦。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[300005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n,Q; cin >> n;
	long long sum = 0;
	for(int i = 1;i <= n;i++) {
		cin >> a[i]; sum += a[i];
	}
	cin >> Q;
	while(Q--) {
		string opt; cin >> opt;
		int x; cin >> x;
		sum += n * x;
		cout << sum << endl;
	}
	return 0;
}

Record

$\large\texttt{Part 3:100 pts}$

我们现在已经知道了怎么快速完成 INFLATION 操作，那 SET 呢？

其实一样啊！把 $x$ 变成了 $y$，不就增加了 $y-x$ 吗？

那怎么统计有多少个值为 $x$ 的呢？

我们用一个桶来存储就可以了。

最后，在加完以后，记得将桶更新，原来所有的 $x$ 都变成了 $y$。

注意 $x=y$ 的特殊情况！

至此，本题就完成了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<long long,long long> mp;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n,Q; cin >> n;
	long long sum = 0,add = 0;
	for(int i = 1;i <= n;i++) {
		long long x; cin >> x; mp[x]++;
		sum += x;
	}
	cin >> Q;
	while(Q--) {
		string opt; cin >> opt;
		if(opt == "INFLATION") {
			int x; cin >> x;
			add += x;
			sum += 1ll * n * x;
			cout << sum << endl;
		}
		else {
			int x,y; cin >> x >> y;
			x -= add; y -= add;
			int cha = y - x;
			sum += 1ll * mp[x] * cha;
			if(x != y) {
				mp[y] += mp[x];
				mp[x] = 0;
			}
			cout << sum << endl;
		}
	}
	return 0;
}

AC Record

$\large\texttt{Part 4}$

总结：这题考察的是桶的思想，以及一点点贡献法，有一定的思维难度，建议评黄。