HNOI/AHOI2018 游戏

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