思路
思考贪心，容易得出我们只有不断往右跳跃才能走得更远。
所以，对于一个线段 \([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;
}
参考文献