自动搬运

查看原文

来自洛谷，原作者为

	Dreamunk **

搬运于2025-08-24 22:00:09，当前版本为作者最后更新于2021-08-05 14:46:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题目

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

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

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

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

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

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

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

  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;
}