#include <cstdio>
#include <iostream>
using namespace std;
const int M = 1000005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,q,s[M],a[M],l[M],r[M],ls[M],tr[M<<2];
void build(int i,int l,int r)
{
	if(l==r) {tr[i]=a[l];return ;}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	tr[i]=max(tr[i<<1],tr[i<<1|1]);
}
int find(int i,int l,int r,int x)
{
	if(tr[i]<=x) return 0;
	if(l==r) return l;
	int mid=(l+r)>>1;
	return tr[i<<1|1]>x?find(i<<1|1,mid+1,r,x):
	find(i<<1,l,mid,x);
}
int ask(int i,int l,int r,int L,int R,int x)
{
	if(L>r || l>R) return 0;
	if(L<=l && r<=R) return find(i,l,r,x);
	int mid=(l+r)>>1,p=ask(i<<1|1,mid+1,r,L,R,x);
	if(p) return p;
	p=ask(i<<1,l,mid,L,R,x);
	return p;
}
int get(int l,int r,int x)
{
	if(l>r) return l;
	int p=ask(1,1,n,l,r,x);
	return p?p+1:l;
}
void init()
{
	build(1,1,n);a[n]=n+1;a[0]=-1;
	for(int i=1;i<=n;i++)
		ls[i]=a[i-1]&&a[i-1]<=i-1?i:ls[i-1];
	for(int i=n,t=0;i>=1;i--)
	{
		l[i]=r[i]=i;
		l[i]=get(ls[i],l[i]-1,r[i]);
		s[++t]=i;
		while(t && (!a[s[t]] || l[i]<=a[s[t]] && a[s[t]]<=r[i]))
		{
			r[i]=s[--t];
			l[i]=get(ls[i],l[i]-1,r[i]);
		}
	}
}
signed main()
{
	n=read();m=read();q=read();
	for(int i=1,x,y;i<=m;i++)
		x=read(),y=read(),a[x]=y;
	init();
	while(q--)
	{
		int x=read(),y=read();
		puts(l[x]<=y && y<=r[x]?"YES":"NO");
	}
}

这题复杂度其实很靠谱的啊，不知道为什么这么多题解说是乱搞。

题目

显然只要求出从每个房间出发能到达的区间。

首先把中间没有锁的房间合并成一个。

考虑一个锁，如果它的钥匙在它左边，那么就不可能从右边打开这个锁；反之亦然。

为了方便，记钥匙在左边的锁为 >，钥匙在右边的锁为 <，房间为 .，那么这一列房间可以长成这种形状：

.<.<.<.>.>.<.

• 对于形如 >.< 的房间，它是永远出不去的，因此答案已经算出来了。

• 对于形如 >.> 的房间，它不能往左边走，考虑一直往右边扩张，扩张的方式是

  1. 答案区间 $[L,R]$ 初始为它本身
  2. 判断房间 $R$ 到房间 $R+1$ 的锁能不能开
  3. 如果开不了，扩张过程结束
  4. 如果开得了，$[L,R]$ 并上从 $R+1$ 出发的答案区间，然后返回第 2 步

  容易发现，这样的过程可以保证一个锁只会被判断一次。

• 对于形如 <.< 的房间，同上。

• 对于形如 <.> 的房间，甚至暴力往两边扩张都是对的，因为它再怎么扩张也只能扩张到形如 >.<.<.<.<.<.>.>.>.>.>.< 的这段房间的一部分，而对于每一个这样的段只会有一个这样的房间做了这个暴力，因此这部分还是线性。

但是实现起来就不用显式地分类讨论，因为四种情况其实都是扩张，写成一个记忆化搜索的样子。

你们的记忆化搜索当然也是长这个样子，所以复杂度也是 $O(n)$。

拓扑排序的做法也是等价的（毕竟拓扑排序后 DP 的题目基本上都可以记忆化搜索）。

#include<bits/stdc++.h>
namespace io{
const int D=1<<21;
char buf[D],*s,*t;
inline char get(){return s==t&&(t=(s=buf)+fread(buf,1,D,stdin),s==t)?-1:*s++;}
inline int read(){
	int a=0;char c=get();
	for(;c< '0'||c> '9';c=get());
	for(;c>='0'&&c<='9';a=a*10+c-'0',c=get());
	return a;
}
}//namespace io
using io::read;
const int N=1e6+3;
int n,m,q,f[N],p[N],l[N],r[N],s[N],t[N];
void Dp(int x){
	if(s[x]&&t[x])return;
	bool fl;
	s[x]=l[x],t[x]=r[x];
	for(;;){
		fl=0;
		if(t[x]<n&&f[t[x]  ]>=s[x]&&f[t[x]  ]<=t[x]){
			Dp(p[t[x]+1]);
			t[x]=t[p[t[x]+1]];
			fl=1;
		}
		if(s[x]>1&&f[s[x]-1]>=s[x]&&f[s[x]-1]<=t[x]){
			Dp(p[s[x]-1]);
			s[x]=s[p[s[x]-1]];
			fl=1;
		}
		if(!fl)break;
	}
}
int main(){
	int x,y;
	n=read(),m=read(),q=read();
	for(int j=1;j<=m;j++)x=read(),y=read(),f[x]=y;
	for(int i=1;i<=n;i++)
		if(i==1||f[i-1])p[i]=l[i]=r[i]=i;
		else p[i]=p[i-1],r[p[i]]=i;
	for(int i=1;i<=n;i++)if(f[i])f[i]=p[f[i]];
	for(int i=1;i<=n;i++)if(p[i]==i)Dp(i);
	for(;q--;)x=read(),y=read(),puts(s[p[x]]<=y&&t[p[x]]>=y?"YES":"NO");
	return 0;
}