原题传送门 https://www.luogu.org/problemnew/show/P4436
\(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;
- }
来源: http://www.bubuko.com/infodetail-2959791.html