CF1859D Andrey and Escape from Capygrad 题解

SunnyYuan的博客 / 2023-08-15 / 原文

思路

思考贪心，容易得出我们只有不断往右跳跃才能走得更远。

所以，对于一个线段 \([l, r]\) 可以轻易到达 \([a, b]\)，那么只对 \([l, b]\) 有用，这些点都可以跳到 \(b\)，\([b + 1, r]\) 这一部分不能往回跳，所以不用考虑。

那么我们就可以把这些线段都当成 \([l, b]\)，然后我们可以想到将所有能到达线段合并（有点并查集的意思）。

对于询问的 \(x\)，可以利用二分找到包含 \(x\) 的线段，输出合并后的线段的右端点作为答案。

代码

#include <bits/stdc++.h>

using namespace std;

struct point {
	int l, r;
	
	bool operator<(const point& b) const {
		return l < b.l;
	}
};

void solve() {
	int n, q;
	vector<point> s;
	set<point> p;
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		int l, r, a, b;
		cin >> l >> r >> a >> b;
		// [l, b]
		s.push_back({l, b});
	}
	sort(s.begin(), s.end());
	
	p.insert({-0x3f3f3f3f, -0x3f3f3f3f});
	p.insert({0x3f3f3f3f, 0x3f3f3f3f});
	for (int i = 0; i < n; i++) {
		int l = s[i].l, r = s[i].r;
		while (i < n - 1 && l <= s[i + 1].l && s[i + 1].l <= r) {
			i++;
			r = max(r, s[i].r);
		}
		p.insert({l, r});
	}
	
	cin >> q;
	
	while (q--) {
		int x;
		cin >> x;
		auto pos = p.upper_bound({x, x});
		pos--;
		if (pos-> l <= x && x <= pos-> r) cout << pos->r << ' ';
		else cout << x << ' ';
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

参考文献

CF1859D 题解