游戏[AHOI/HNOI2018]

发表于 分类于 ，

题目链接

loj

题解

一开始看错题了。。。浪费了好久的时间。

首先经过胡乱分析发现，一个点能走到的点集是一个区间。

因此对于每个点 $i$，求出这个 $[l_i,r_i]$ 区间，然后就可以 $O(1)$ 判断了。

对于一个门，我们假设 $x$ 向 $y$ 连一条边。

前 $20%$ 的很简单，我们只需考虑 $y\leq x$ 的 $40$ 分。

$y\leq x$

这一部分保证了钥匙一定在门的左侧。

也就是说，如果你往左走，碰到了一扇门，那么你就没了，你一定走不过这扇门。那么，$l_i$ 的值就很容易求出来了。

现在来看看 $r_i$ 怎么求。如果某个点 $i$ 能走到 $r_i$，且另外一个点 $j$ 能走到 $i$，那么 $r_j$ 就至少是 $r_i$ 了。

可以用一个单调栈，里面存当前情况下，被门隔开的所有区间。从后往前枚举每个线段，判断这个区间是否能和栈顶的区间合并（也就是这个门能否被打开），如果可以就并到一起。

判断一个门能否打开相当于判断这个钥匙是否在当前区间内。

时间复杂度 $O(n)$。

$100%$

这时候，如果按照上面的方法从右往左做，$l_i$ 是会发生改变。

但是，你发现它还是不能从右往左跨过 $y\leq x$ 的门。

那么当一个 $[l_i,r_i]$ 的右端点变大之后，$l_i$ 能去到哪里呢？

显然最多最多不会超过第一个 $y\leq x$ 的门，记这个为 $le_i$。

那么在 $[le_i,l_i)$ 里面，这些门都是向右指的。

对于当前离 $l_i$ 最近的门（其实就是 $l_i$），如果它的钥匙在 $\leq r$ 处，那么这扇门就可以开。

也就是在 $[le_i,l_i)$ 中找到第一个离 $l_i$ 最近的，且钥匙 $>r$ 的门。

用个线段树即可。时间复杂度 $O(n\log n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=1e6+5;
int n,m,key[N],l[N],r[N],le[N];
int st[N],top;

int mx[N<<2];
#define lc (u<<1)
#define rc (u<<1|1)
void build(int u,int l,int r)
{
    if(l==r) return (void)(mx[u]=key[l]);
    int mid=l+r>>1;
    build(lc,l,mid); build(rc,mid+1,r);
    mx[u]=max(mx[lc],mx[rc]);
}
int ask(int u,int l,int r,int L,int R,int x)
{
    if(l==r) return l;
    int mid=l+r>>1,ans=0;
    if(mid<R&&mx[rc]>x) ans=ask(rc,mid+1,r,L,R,x);
    if(!ans&&L<=mid&&mx[lc]>x) ans=ask(lc,l,mid,L,R,x);
    return ans;
}
inline bool check(int x)
{
    int tmp=ask(1,1,n,le[x],l[x]-1,r[x]);
    l[x]=tmp?tmp+1:le[x];
    return l[x]<=key[r[x]]&&key[r[x]]<=r[x];
}
int main()
{
    n=read(); m=read(); int T=read();
    int x,y;
    fo(i,1,m) x=read(),key[x]=read();
    build(1,1,n);
    for(int i=1,j;i<=n;i=j+1)
    {
        for(j=i;j<n&&!key[j];j++);
        for(int k=i;k<=j;k++) l[k]=i,r[k]=j;
    }
    for(int i=1,j=1;i<=n;le[i++]=j)
        if(key[i-1]&&key[i-1]<i)
            j=i;
    fd(i,n,1) for(st[++top]=r[i];top&&check(i);r[i]=st[--top]);
    for(;T--;puts((l[x]<=y&&y<=r[x])?"YES":"NO")) x=read(),y=read();
    return 0;
}