题解 P4436 【[HNOI/AHOI2018]游戏】
teafrogsf
2018-04-28 18:14:05
~~跑的也太慢了吧......被暴力吊起来打~~
这题目的思路其实很简单:首先$\Theta(n)$处理出每个点一开始能到达的点,然后对于每个门,如果当前门的钥匙在左边那么就$\rm add(i+1,i)$,否则$\rm add(i,i+1)$,这样的意思是从$i+1$到不了$i$,反之亦然。
然后我们按照拓扑序进行遍历,每次暴力左右跳求当前点能得到的答案。我们可以发现,每次暴力跳的左右边界一定不会超过拓扑序列中还没有的位置能给予的贡献,所以总跳跃次数(或许)为$\Theta(n)$,于是这(或许)可以被证明是$\Theta(n)$的。
~~函数名比较闲着没事干请不要在意~~
**另外,有一个小优化:其实我们可以在一开始缩点,之后对于每个缩后的点执行这个过程就可以了。**这样应该会更快一些,然而因为我过了这道题就不想打了。有兴趣的各位可以尝试一下。
~~此外初始化拓扑的队列时倒着加会快不少~~
```cpp
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstdlib>
#define neko 1000010
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-(i)))
#define travel(i,u,v) for(register int i=head[u],v=e[i].v;i;i=e[i].next,v=e[i].v)
int n,m,q,t;
typedef int arr[neko];
arr key,L,R,dgr,head;
struct node
{
int v,next;
}e[neko];
void add(int x,int y)
{
e[++t].v=y;
e[t].next=head[x];
head[x]=t,++dgr[y];
}
namespace solve
{
using namespace std;
void contraction()
{
int now=1;
f(i,1,n){L[i]=now;if(key[i])now=i+1;}now=n;
rf(i,n,1){R[i]=now;if(key[i-1])now=i-1;}
}
bool check(int pos,int now)
{
if(!key[pos])return 1;
if(key[pos]>=L[now]&&key[pos]<=R[now])return 1;
return 0;
}
void monotonestack()
{
bool flag;int x;
queue<int>q;rf(i,n,1)if(!dgr[i])q.push(i);
while(!q.empty())
{
x=q.front(),q.pop();
flag=1;
while(flag)
{
flag=0;
while(L[x]>1&&check(L[x]-1,x))L[x]=L[L[x]-1],flag=1;
while(R[x]<n&&check(R[x],x))R[x]=R[R[x]+1],flag=1;
}travel(i,x,v)if(!(--dgr[v]))q.push(v);
}
}
}
char getc()
{
static char buf[1048576],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1048576,stdin),p1==p2)?EOF:*p1++;
}
void read(int &x)
{
char c=getc();x=0;
while(!isdigit(c))c=getc();
while(isdigit(c))x=(x<<1)+(x<<3)+(c^'0'),c=getc();
}
int main()
{
int x,y;
read(n),read(m),read(q);
f(i,1,m){read(x),read(y),key[x]=y;if(y<=x)add(i+1,i);else add(i,i+1);}
solve::contraction(),solve::monotonestack();
f(i,1,q)
{
read(x),read(y);
if(x>y&&L[x]<=y)putchar('Y'),putchar('E'),putchar('S'),putchar('\n');
else if(x<=y&&R[x]>=y)putchar('Y'),putchar('E'),putchar('S'),putchar('\n');
else putchar('N'),putchar('O'),putchar('\n');
}
}
```