【题解】Luogu P4436 [HNOI/AHOI2018]游戏

原题传送门

\(n^2\)过百万在HNOI/AHOI2018中真的成功了qwqwq

先将没门分格的地方连起来，枚举每一个块，看向左向右最多能走多远，最坏复杂度\(O(n^2)\)，但出题人竟然没卡（建议JSOI的出题人好好学学）

#include <bits/stdc++.h>
#define N 1000005
#define getchar nc
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
int n,m,q; 
int a[N],is[N],vis[N],l[N],r[N];
inline void dfs(register int x)
{
    if(vis[x])
        return;
    int L=x,R=x,ok;
    do{
        ok=0;
        if(L<=a[L-1]&&a[L-1]<=R)
        {
            ok=1;
            dfs(L-1);
            L=l[L-1];
        }
        if(L<=a[R]&&a[R]<=R)
        {
            ok=1;
            dfs(R+1);
            R=r[R+1];
        }
    }while(ok);
    l[x]=L,r[x]=R;
    vis[x]=1;
}
int main()
{
    n=read(),m=read(),q=read();
    for(register int i=1;i<=m;++i)
    {
        int x=read(),y=read();
        a[x]=y;
    }
    is[1]=1;
    for(register int i=1;i<=n;++i)
    {
        is[i+1]=is[i];
        if(a[i])
            ++is[i+1];
    }
    ++m;
    for(register int i=1;i<=n;++i)
        if(a[i])
            a[is[i]]=is[a[i]];
    for(register int i=1;i<=m;++i)
        dfs(i);
    while(q--)
    {
        int x=is[read()],y=is[read()];
        if(l[x]<=y&&y<=r[x])
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

【题解】Luogu P4436 [HNOI/AHOI2018]游戏

原文：https://www.cnblogs.com/yzhang-rp-inf/p/10398062.html