- 显然从点 (x) 出发,能到达的点是包含 (x) 的一段区间.用 (L,R) 两个数组记录每个点对应的区间端点.
- 如果能预处理出 (L,R) ,询问显然可以 (O(1)) 回答.
- 先考虑最朴素的暴力,枚举每个点 (x) ,从 (x) 往两边跳,如果去下个点的门没有锁,或者钥匙的位置在 ([L_x,R_x]) 内,就继续拓展.
- 有一个比较简单的优化,拓展到了一个点 (y) 后,就用 (y) 的 (L,R) 值更新 (x) 的.这样做能获得 (20) 分的好成绩.
- 为了使这个优化减少更多的跳跃次数(???不负责口胡),我们对枚举 (x) 的顺序随机化,执行上述的算法.
- 实践可以获得 (100) 分. 这样做期望大概是 (O(nlogn)) 的?但我不会证.如果求出了期望时间复杂度,请务必告知.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXN=1e6+10;
int n,m,Q;
int ord[MAXN];
int L[MAXN],R[MAXN],a[MAXN];
void solve(int x)
{
int l=x,r=x;
while(1)
{
int f=0;
if(l>1 && (!a[l-1] || (l<=a[l-1] && a[l-1]<=r)))
f=1,--l,l=min(l,L[l]),r=max(r,R[l]);
if(r<n && (!a[r] || (l<=a[r] && a[r]<=r)))
f=1,++r,l=min(l,L[r]),r=max(r,R[r]);
if(!f)
break;
}
L[x]=l,R[x]=r;
}
int main()
{
n=read(),m=read(),Q=read();
for(int i=1;i<=m;++i)
{
int x=read(),y=read();
a[x]=y;
}
for(int i=1;i<=n;++i)
ord[i]=i,L[i]=n+1,R[i]=0;
srand(19260817);
random_shuffle(ord+1,ord+1+n);
for(int i=1;i<=n;++i)
solve(ord[i]);
while(Q--)
{
int s=read(),t=read();
if(L[s]<=t && t<=R[s])
puts("YES");
else
puts("NO");
}
return 0;
}