[HNOI/AHOI2018]游戏

题目链接

https://loj.ac/problem/2508
https://www.lydsy.com/JudgeOnline/problem.php?id=5288
https://www.luogu.org/problemnew/show/P4436

思路

离散化没啥好说的
一堵墙
左边是i，右边是i+1
如果钥匙在墙的左边，那么右边永远过不去左边（拿不到钥匙）
那就右边向左边连边
就是先处理左边，等全部处理完了再去处理右边
然后拓扑上面暴力弄就好了
听着好像分治呀

吐槽

不过这数据好垃圾呀，随机处理也可以过
我写错了代码还90、、、

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,js,m,p,hav[N],belong[N],wall[N],L[N],R[N],ru[N],q[N];
struct node {
    int v,nxt;
}e[N];
int head[N],tot;
inline void add(int u,int v) {
    // cout<<u<<" "<<v<<" !\n";
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
inline int max(int a,int b) {return a>b?a:b;}
inline int min(int a,int b) {return a>b?b:a;}
int main() {
    // freopen("game8.in","r",stdin);
    // freopen("a.out","w",stdout);
    n=read(),m=read(),p=read();
    for(int i=1;i<=m;++i) hav[read()]=read();
    js=1;
    for(int i=1,l=1,r=1;i<=n;++i) {
        belong[i]=js;
        if(hav[i]) js++;
    }
    js=belong[n];
    for(int i=1;i<=n;++i) {
        if(hav[i]) {
            wall[belong[i]]=belong[hav[i]];
            if(hav[i]>i) add(belong[i],belong[i+1]),ru[belong[i+1]]++;
            else add(belong[i+1],belong[i]),ru[belong[i]]++;
            // cout<<x<<" "<<y<<"<\n";
        }
    }
    for(int i=1;i<=js;++i) {
        L[i]=R[i]=i;
        if(!ru[i]) q[++q[0]]=i;
    }
    int mmp=0;
    while(q[0]) {
        int u=q[q[0]];
        q[0]--;
        // cout<<u<<"  <<<<<<u\n";
        for(int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            // cout<<u<<" -> " <<v<<"\n";
            ru[v]--;
            while (233) {
                int flag=true;
                while (L[v] <= wall[R[v]] && wall[R[v]] <= R[v] && R[v]<=js) {
                    flag=false;
                    L[v]=min(L[v],L[R[v]+1]);
                    R[v]=max(R[v],R[R[v]+1]);
                }
                while (L[v] <= wall[L[v] - 1] && wall[L[v] - 1] <= R[v] && L[v] > 1) {
                    flag=false;
                    L[v]=min(L[v],L[L[v]-1]);
                    R[v]=max(R[v],R[L[v]-1]);
                }
                if(flag) break;
            }
            if(!ru[v]) q[++q[0]]=v;
        }
    }
    // for(int i=1;i<=js;++i) cout<<L[i]<<" "<<R[i]<<"<\n";
    for(int i=1;i<=p;++i) {
        int S=read(),T=read();
        if(L[belong[S]]<=belong[T]&&belong[T]<=R[belong[S]]) puts("YES");
        else puts("NO");
    }
    return 0;
}