自动搬运

查看原文

来自洛谷，原作者为

	Twlight！ 追求真理之人不可心存傲慢，不可嘲笑无法用科学解释的奇迹，不可回避这个世界的美丽。

搬运于2025-08-24 23:10:16，当前版本为作者最后更新于2025-02-26 20:20:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现做法唐了，回来重新思考。

如果没有修改操作，我们可以直接 $O(n)$ 算出答案，于是我们考虑每次操作会改变什么。

其实影响最终温度的只有相邻两地的相对海拔差，每次给一个区间的海拔加减，这个区间内的相对海拔差是不会变的，只有区间左右两边相邻的海拔差会改变，考虑使用差分数组维护，每次动态更新答案即可。

时间复杂度：$O(n + q)$，注意本题要开 long long。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int ll

const int N = 1000000 + 10;
const int inf = 1e9 + 7;
using namespace std;

inline int read () {
	int x = 0, k = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') k = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return (1ll * x * k);
}

int n, q, s, t, ret;
int a[N], b[N]; 

int calc (int x) {
	if (x > 0) return x * t;
	else return x * s;
}

signed main() {
	n = read(), q = read(), s = read(), t = read();
	for (int i = 0; i <= n; ++i) a[i] = read();
	for (int i = 1; i <= n; ++i) b[i] = a[i - 1] - a[i], ret += calc(b[i]);
	for (int i = 1; i <= q; ++i) {
		int l = read(), r = read(), x = read();
		ret -= calc(b[l]), ret -= (r < n) * calc(b[r + 1]);
		b[l] -= x, b[r + 1] += x;
		ret += calc(b[l]), ret += (r < n) * calc(b[r + 1]);
		cout << ret << endl;
	}
	return 0;
}