题解

思路概述

• 把房间按锁的位置分成若干连续区间：每当门 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;
}