题解

思路概述

• 把房间按锁的位置分成若干连续区间：每当门 i 有锁，就把序列在 i 分割成左/右两段。每段 [lf, rf] 初始只包含本区间的房间。
• 若锁钥匙在左段，则右段要想打开必须先完成左段；这在区间之间形成了一条依赖边。反之亦然。
• 将这些依赖关系构成 DAG 并做拓扑排序，从“无前驱”的区间开始，逐步扩张其可达区间 [L,R]（代表可以畅通的房间范围）。当一个区间的依赖全部满足后，solve() 通过拓展左右端点使得新的区间覆盖尽量大。
• 最终每个房间属于某个分段 bl[x]，区间的可达范围 L[bl], R[bl] 即可用于回答询问 (S, T)：若 T 在 bl[S] 对应的 [L,R] 内，则可达，否则不可达。

复杂度

• 建图 + 拓扑排序 + 区间扩张总计 O(n + m)；查询只需 O(1) 判定。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
int n, m, q, qx, qy, cnt, tot, ptt, head[N], du[N], bl[N], x[N], y[N], L[N], R[N], lc[N];
int lf[N], rf[N];
struct dcz {
    int nex, to;
} a[2 * N];
void add(int x, int y) {
    a[++cnt].nex = head[x];
    a[cnt].to = y;
    head[x] = cnt;
}
void solve(int x) {
    L[x] = lf[x], R[x] = rf[x];

    while (1) {
        bool f = 0;
        ptt++;
        assert(ptt < 2e8);

        if (R[x] < n && lc[R[x]] <= R[x] && lc[R[x]] >= L[x]) {
            f = 1;
            R[x] = R[bl[R[x] + 1]];
        }

        if (L[x] > 1 && lc[L[x] - 1] <= R[x] && lc[L[x] - 1] >= L[x]) {
            f = 1;
            L[x] = L[bl[L[x] - 1]];
        }

        if (!f)
            return;
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;

    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        lc[x[i]] = y[i];
    }

    ++tot;
    lf[tot] = 1;

    for (int i = 1; i <= n; i++) {
        bl[i] = tot;

        if (lc[i] && i != n) {
            rf[tot] = i;
            tot++;
            lf[tot] = i + 1;

            if (lc[i] <= i) {
                add(tot, tot - 1);
                du[tot - 1]++;
            } else {
                add(tot - 1, tot);
                du[tot]++;
            }
        }
    }

    rf[tot] = n;
    queue<int> qq;

    for (int i = 1; i <= tot; i++) {
        if (!du[i])
            qq.push(i);
    }

    while (qq.size()) {
        int u = qq.front();
        qq.pop();
        solve(u);

        for (int i = head[u]; i; i = a[i].nex) {
            int v = a[i].to;

            if (!(--du[v]))
                qq.push(v);
        }
    }

    for (int i = 1; i <= q; i++) {
        cin >> qx >> qy;

        if (L[bl[qx]] <= qy && R[bl[qx]] >= qy)
            cout << "YES\n";
        else
            cout << "NO\n";
    }

    return 0;
}