题目描述
题解
这道题其实是让我们对于每个位置，求出它的一个合法区间。
先考虑如果所有的限制都满足y<=x的限制，说明如果我们如果从一个点出发，就不用来回跑腿了，直接一路向右走就好了。
那么这时对于每个点，它能扩展到的最左的点就是他向左遇到的第一个门，至于右端点，我们可以倒着扫描一个序列，维护一个栈，如果栈顶在当前是可达的，那么我们就把它弹掉，因为这个点在任何时候度不会成为端点了。
如何解释？要么这个点在将来也可以被通过，要么存在比它更靠前的一个点变成右端点。
然后这样是O(n)的。
如果我们这个限制，我们不能直接卡出左端点，可以考虑边界条件，先卡出一个满足没有y<=x的左端点，这是里面所有的限制都是y>x的，那么不可达的情况就是y大于当前的右端点，所以我们要找到的就是最靠右的满足前面那个条件的点。
这个用线段树维护，结合前面的栈可以做到O(nlogn)。
代码
#include<iostream> #include<cstdio> #define N 1000002 using namespace std; int n,m,q,tr[N<<2],key[N],st[N],lim[N],top,l[N],r[N]; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } int work(int cnt,int l,int r,int x){ if(tr[cnt]<=x)return 0; if(l==r)return l; int mid=(l+r)>>1; if(tr[cnt<<1|1]>x)return work(cnt<<1|1,mid+1,r,x); else return work(cnt<<1,l,mid,x); } int query(int cnt,int l,int r,int L,int R,int x){ if(l>=L&&r<=R)return work(cnt,l,r,x); int mid=(l+r)>>1,ans=0; if(mid<R)ans=query(cnt<<1|1,mid+1,r,L,R,x); if(ans)return ans; if(mid>=L)ans=query(cnt<<1,l,mid,L,R,x); return ans; } void build(int cnt,int l,int r){ if(l==r){tr[cnt]=key[l];return;} int mid=(l+r)>>1; build(cnt<<1,l,mid);build(cnt<<1|1,mid+1,r); tr[cnt]=max(tr[cnt<<1],tr[cnt<<1|1]); } inline int solve(int l,int r,int x){ if(l>r)return l; int pos=query(1,1,n,l,r,x); if(!pos)return l;else return pos+1; } int main(){ n=rd();m=rd();q=rd();int x,y; for(int i=1;i<=m;++i){ x=rd();y=rd(); key[x]=y; } build(1,1,n); lim[1]=1; for(int i=2;i<=n;++i)lim[i]=(key[i-1]&&key[i-1]<=i-1)?i:lim[i-1]; key[n]=n+1; for(int i=n;i>=1;--i){ l[i]=r[i]=i; l[i]=solve(lim[i],i-1,r[i]); st[++top]=i; while(top&&((key[st[top]]>=l[i]&&key[st[top]]<=r[i])||(!key[st[top]]))){ --top; r[i]=st[top]; l[i]=solve(lim[i],i-1,r[i]); } } while(q--){ x=rd();y=rd(); if(l[x]<=y&&y<=r[x])puts("YES"); else puts("NO"); } return 0; }