[ARC073F] Many Moves 题解

个人感觉其实还挺套路的题目。不配紫题。

对于两个玩意在数轴上跑来跑去这种题目，常见的套路是固定一个点的位置，用另一个点的位置设为状态。

对于本题，题目已经帮你固定了一个点，于是我们设 \(dp_{x}\) 表示一个点在当前要求的位置，另一个点在 \(x\) 的最小时间，转移就是分类讨论转移到 \(x\) 的点上一次是在上一个要求的位置还是在别的其他地方即可，需要支持区间加的线段树。

时间复杂度 \(O(n\log n)\)。

代码：

#include <bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
int n, q, sx, sy;
const int inf = 1e16;
struct Seg {
	struct Node {
		int l, r;
		int flg;
		int minn;
	} e[N << 2];
	#define l(i) e[i].l
	#define r(i) e[i].r
	#define fg(i) e[i].flg
	#define mn(i) e[i].minn
	#define lc (p << 1)
	#define rc (lc | 1)
	void push_up(int p) {
		mn(p) = min(mn(lc), mn(rc));
	}
	void build(int p, int l, int r) {
		l(p) = l, r(p) = r;
		if (l == r)
			return mn(p) = inf, void();
		int mid = (l + r) >> 1;
		build(lc, l, mid);
		build(rc, mid + 1, r);
		push_up(p);
	}
	void push_down(int p) {
		if (fg(p) == 0)
			return;
		mn(lc) += fg(p);
		mn(rc) += fg(p);
		fg(lc) += fg(p);
		fg(rc) += fg(p);
		fg(p) = 0;
	} 
	void update(int p, int x, int val) {
		if (l(p) == r(p) && l(p) == x) 
			return mn(p) = min(mn(p), val), void();
		push_down(p);
		int mid = (l(p) + r(p)) >> 1;
		if (x <= mid)
			update(lc, x, val);
		else
			update(rc, x, val);
		push_up(p);
	}
	void change(int p, int l, int r, int val) {
		if (l > r || l(p) > r || l > r(p))
			return;
		if (l <= l(p) && r(p) <= r) {
			fg(p) += val;
			mn(p) += val;
			return;
		}
		push_down(p);
		change(lc, l, r, val);
		change(rc, l, r, val);
		push_up(p);
	}
	int query(int p, int l, int r) {
		if (l > r || l(p) > r || l > r(p))
			return inf;
		if (l <= l(p) && r(p) <= r)
			return mn(p);
		push_down(p);
		return min(query(lc, l, r), query(rc, l, r));
	}
} A, B;
int lst, nw;
signed main() {
	cin >> n >> q >> sx >> sy;
	cin >> nw;
	A.build(1, 1, n);
	B.build(1, 1, n);
	int t = abs(sy - nw);
	A.update(1, sx, t + sx);
	B.update(1, sx, t - sx);
	t = abs(sx - nw); 
	A.update(1, sy, t + sy);
	B.update(1, sy, t - sy);
	for (int i = 1; i < q; i++) {
		lst = nw;
		cin >> nw;
		int t = min(A.query(1, nw, n) - nw, B.query(1, 1, nw) + nw);
		A.change(1, 1, n, abs(nw - lst));
		B.change(1, 1, n, abs(nw - lst));
		A.update(1, lst, t + lst);
		B.update(1, lst, t - lst);
	}
	int ans = inf;
	for (int i = 1; i <= n; i++) 
		ans = min(ans, A.query(1, i, i) - i);
	cout << ans << "\n";
	return 0;
	
}