526互联

Educational Codeforces Round 132 (Rated for Div. 2) B. Also Try Minecraft

发布时间 2023-09-10 21:03:06作者: zsxuan

一个世界地图用一个长为 \(n\) 的数组表示，\(a_i\) 代表坐标 \(i\) 的高度。若下一块区域的高度为 \(y\) ，当前区域的高度为 \(x\) ，则一次行走会受到 \(max(y - x, 0)\) 点下落伤害。

有 \(q\) 个询问，每个询问独立，给定起点和终点坐标 \(s, t\) ，回答每次受到多少点下落伤害。

不妨设 \(pre\) 数组和 \(suf\) 数组，\(pre_i = \sum_{j = 1}^{i} max(a[i - 1] - a[i], 0)\) ，\(suf_i = \sum_{j = i}^{n} max(a[i + 1] - a[i], 0)\) 。代表到达 \(i\) 坐标受到的下落伤害总和。（显然这是个边权问题）

因为每段区间受到的伤害独立，符合加法原理，于是可以由前缀和差分得到每段的伤害。

  • 若 \(t \geq s\) ，则 \(ans = pre_t - pre_{s}\) 。
  • 否则 \(ans = suf_t - suf_{s}\) 。

因为带权的是边而不是点，所以不考虑区间容斥，或区间开闭。

view 
#include <bits/stdc++.h>
void solve() {
	int n, q; std::cin >> n >> q;
	std::vector<long long> a(n+2), pre(n+2), suf(n+2);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) pre[i] = std::max(0LL, a[i - 1] - a[i]) + pre[i - 1];
	for (int i = n; i; --i) suf[i] = std::max(0LL, a[i + 1] - a[i]) + suf[i + 1];
	for (int i = 0; i < q; i++) {
		int s, t; std::cin >> s >> t;
		if (t >= s) std::cout << pre[t] - pre[s] << '\n';
		else std::cout << suf[t] - suf[s] << '\n';
	}
}
signed main() {
	int _ = 1; //std::cin >> _;
	while (_--) solve();
	return 0;
}