CF1859D Andrey and Escape from Capygrad

CF1859D Andrey and Escape from Capygrad 题解。

题目大意

给定 $n$ 对区间，每对区间由大区间 $[l_i,r_i]$ 和小区间 $[a_i,b_i]$ 构成，保证小区间是大区间的子区间。在任意时间，你可以任意多次使用（可以不使用）以下技能来改变你的当前位置：

• 选择一个数 $i(1\le i\le n)$ ，满足你当前位置在第 $i$ 对区间的大区间内，则你可以立即传送到这对区间的小区间里的你指定的任意位置。

$q$ 组询问，每组询问给定一个初始位置 $x$ ，回答当你初始位置为 $x$ 时，你能只通过传送技能传送到的最大位置。

思路

贪心的考虑，如果使用传送，每次传送一定传送到 $b_i$ 上是最优的（如果只在当前区间内传送，显然这样是最优的；如果仍需要使用另一个区间的传送功能，那么如果另一个区间在当前 $[a_i,b_i]$ 内部，则效果不如 $b_i$，不如不传，如果在外部，则传送到 $b_i$ 显然更容易到达另一个区间）。

并且，我们只会在 $[l,b]$ 内部使用传送功能，在其它区域内不如不传。那么很容易想到直接对 $[l,b]$ 做区间合并，然后离线询问扫描线即可。

代码

int n, l, r, aa, bb, t, curr, tot, res[maxN + 5];
struct sgm {
    int l, r;
} a[maxN + 5], b[maxN + 5];
struct node {
    int qry, id;
} q[maxN + 5];
void solve() {
    tot = 0;
    cin >> n;
    rep(i, 1, n) {
        cin >> l >> r >> aa >> bb;
        a[i] = {l, bb};
    }
    sort(a + 1, a + 1 + n, [](sgm x, sgm y) { return x.l < y.l; });
    b[++tot] = a[1];
    rep(i, 2, n) {
        if (a[i].l <= b[tot].r) {
            b[tot].r = max(a[i].r, b[tot].r);
        } else {
            b[++tot] = a[i];
        }
    }
    cin >> t;
    rep(i, 1, t) {
        cin >> q[i].qry;
        q[i].id = i;
    }
    sort(q + 1, q + 1 + t, [](node x, node y) { return x.qry < y.qry; });
    curr = 1;
    rep(i, 1, t) {
        while (q[i].qry > b[curr].r && curr <= tot)
            curr++;
        if (curr > tot || q[i].qry < b[curr].l) {
            res[q[i].id] = q[i].qry;
        } else {
            res[q[i].id] = b[curr].r;
        }
    }
    sort(q + 1, q + 1 + t, [](node x, node y) { return x.id < y.id; });
    rep(i, 1, t) { cout << res[i] << " "; }
    cout << endl;
}