【AHOI2018】游戏

题面

https://www.luogu.org/problem/P4436

题解

先预处理出每个地方的视野，再在线回答询问。

首先，如果是从另外一个地方进入一个地方，会无条件获得这个地方的视野。

门一定是从某一边进入另外一边。

把门看成一条边，拓扑排序一遍。

沿拓扑序从大到小暴力拓展，这样每个区域只会被拓展一次。

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000500
#define ri register int
using namespace std;

int n,m,k,fa[N],tup[N],L[N],R[N],key[N],ru[N];
vector<int> to[N];

inline int read() {
  int ret=0,f=0; char ch=getchar();
  while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
  while (ch>='0' && ch<='9') ret*=10,ret+=(ch-'0'),ch=getchar();
  return f?-ret:ret;
}

int getf(int x) {
  if (fa[x]==x) return x;
  return fa[x]=getf(fa[x]);
}

void work(int x) {
  while (1) {
    int nl=L[x],nr=R[x];
    while (L[x]>1 && L[x]<=key[getf(L[x]-1)] && key[getf(L[x]-1)]<=R[x]) L[x]=L[getf(L[x]-1)];
    while (R[x]<n && L[x]<=key[getf(R[x])] && key[getf(R[x])]<=R[x]) R[x]=R[getf(R[x]+1)];
    if (L[x]==nl && R[x]==nr) return;
  }
}

int main(){
  n=read(); m=read(); k=read();
  for (ri i=1;i<=m;i++) {
    int x=read(),y=read();
    key[x]=y;
  }
  for (ri i=1;i<=n;i++) fa[i]=i;
  for (ri i=n-1;i>=1;i--) if (!key[i]) fa[i]=getf(i+1);

  for (ri i=1;i<=n;i++) if (key[i]) {
    if (key[i]<=i) to[getf(i)].push_back(getf(i+1)),ru[getf(i+1)]++;
    else to[getf(i+1)].push_back(getf(i)),ru[getf(i)]++;
  }
  
  queue<int> Q;
  for (ri i=1;i<=n;i++) if (!ru[getf(i)] && getf(i)==i) Q.push(i);
  int cc=0;
  while (!Q.empty()) {
    int x=Q.front(); Q.pop();
    tup[++cc]=x;
    for (ri i=0;i<to[x].size();i++) {
      int y=to[x][i];
      ru[y]--;
      if (!ru[y]) Q.push(y);
    }
  }
  for (ri i=1;i<=n;i++) if (key[i]) key[getf(i)]=key[i];

  for (ri i=n;i>=1;i--) L[getf(i)]=i;
  for (ri i=1;i<=n;i++) R[getf(i)]=i;
  for (ri i=n;i>=1;i--) work(tup[i]);
  for (ri i=1;i<=k;i++) {
    int s=getf(read()),t=read();
    if (L[s]<=t && t<=R[s]) puts("YES"); else puts("NO");
  }
  return 0;
}