之后的题解没有必要都会省去 Problem。
话说为什么要坚持写这个题解呢，因为有学长说，每做一题记得把解法写下来，就算一句话也行。

我觉得也挺有道理。为什么不单独开一篇文章记录一句话题解呢，因为我感觉那样还麻烦一点。（反正就是不想）

Solution

考虑如果一个钥匙在一个门的左边，那么右边一定经过不了这扇门去左边。

那么就可以得到一个拓扑的扩展顺序，并且按顺序拓扑可以将复杂度控制在 $O(n)$ 左右。

相邻格子的重编号需要注意。 能用数组写的不要上并查集。

Code

// Code by ajcxsu
// Problem: game

#include<bits/stdc++.h>
#define qua N
using namespace std;

const int N=1e6+10;
int mea[qua];
int fa[N], l[N], r[N];
int n;
int h[N], to[N], nexp[N], in[N], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, in[b]++, p++; }
inline bool bel(int x, int l, int r) { return x>=l && x<=r; }
int idx[N];
int qu[N], head=0, tail=0, na;
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int m, q;
    cin>>n>>m>>q;
    int u, v;
    for(int i=0;i<m;i++) cin>>u>>v, mea[u]=v;
    int id=1;
    l[1]=r[1]=1;
    for(int i=1;i<=n;i++) {
        idx[i]=id;
        if(mea[i]) {
            ++id; l[id]=r[id]=id;
            if(mea[i]<=i) ins(id, id-1);
            else ins(id-1, id);
        }
    }
    for(int i=1;i<=n;i++) if(mea[i]) {
        mea[idx[i]]=idx[mea[i]];
        if(i!=idx[i]) mea[i]=0;
    }
    for(int i=1;i<=id;i++) if(!in[i]) qu[tail++]=i;
    while(head<tail) {
        na=qu[head++];
        while(bel(mea[l[na]-1], l[na], r[na]) || bel(mea[r[na]], l[na], r[na])) {
            if(bel(mea[l[na]-1], l[na], r[na])) l[na]=l[l[na]-1];
            if(bel(mea[r[na]], l[na], r[na])) r[na]=r[r[na]+1];
        }
        for(int u=h[na];u;u=nexp[u]) {
            in[to[u]]--; if(!in[to[u]]) qu[tail++]=to[u];
        }
    }
    while(q--) {
        cin>>u>>v;
        cout<<(bel(idx[v], l[idx[u]], r[idx[u]])?"YES\n":"NO\n");
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-hnoi2018-game.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆