[HNOI/AHOI2018]游戏

暴力

题面

游戏规则复杂

• 对于$20pts$ $n\leq1000$
• 对于另外$40pts$ $key[i]\leq i$
• 对于$60pts$ $n\leq10^5$
• 对于$100pts$ $n\leq10^6$
  （数据水的连暴力都卡不掉)

解析

话说我在考场上想到这道题在$ZJOI2018Round 1$讲过，然而我忘解法了。。。

$n\leq1000$

模拟大法好

$key[i]\leq i$

在该情景下，我们只能往右走。
于是我们预处理一下某点能到达的最右端点即可。
啥？不会维护？
初始化每个点能到达的最右点，然后每次跑$1-n$判断能否跳到该点最右点的最右点，能就更新，跑到不能更新即可。
最大复杂度为$O(n^2)$，但肯定不满。

乱搞$n\leq10^6$

改进上面方法，同时维护每点能到的最左点即可。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e6+100;
int n,m,p,pos[N],l[N],r[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'|ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();p=gi();
  fp(i,1,m)
    {
      re int x=gi(),y=gi();pos[x]=y;
    }
  fp(i,1,n) l[i]=r[i]=i;
  fp(i,2,n)
    if(!pos[i-1]) l[i]=l[i-1];
  fq(i,n-1,1)
    if(!pos[i]) r[i]=r[i+1];
  re int flag=1;
  while(flag)
    {
      flag=0;
      fp(i,2,n)
        while(l[i]>1&&pos[l[i]-1]>=l[i]&&pos[l[i]-1]<=r[i]) l[i]=l[l[i]-1],flag=1;
      fq(i,n-1,1)
    while(r[i]<n&&pos[r[i]]>=l[i]&&pos[r[i]]<=r[i]) r[i]=r[r[i]+1],flag=1;
    }
  fp(i,1,p)
    {
      re int s=gi(),t=gi();
      if(l[s]<=t&&t<=r[s]) puts("YES");else puts("NO");
    }
  return 0;
}

$n\leq10^6$

考虑一扇门，如果钥匙在左边，那么右边的永远到不了左边。那么我们从左边向右边连一条边，表示右边要在左边之前处理。因为如果左边能到右边，那么右边能走到的区间被左边能走到的区间包含。反之同理。
　 然后我们按拓扑序处理。每次判断当前区间是否能向两边走，如果可以，就继续拓展，然后把这个区间的范围扩大（将拓展的区间并入）。由于每个区间最多被并入$2$次（一次左边一次右边）所以复杂度是$O(n)$。
　 但是由于数据过水，和$O(n^2)$算法时间差不多？？？

# include <bits/stdc++.h>
# define    N       1000100
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
struct node{
    int b,s;
}p[N];
bool cmp(node x, node y){
    return x.b<y.b;
}
int n,m,tmp,num,id[N],cnt[N],q[N],mxl[N],mxr[N];
bool tag[N],l[N],r[N];
int main(){
    n=read(), m=read(), tmp=read();
    for (int i=1; i<=m; i++){
        p[i].b=read(), p[i].s=read();
        tag[p[i].b]=true;
    }
    sort(p+1,p+m+1,cmp);
    num=1;
    for (int i=1; i<=n; i++){
        id[i]=num;
        if (tag[i]==true) num++;
    }
    for (int i=1; i<=m; i++){
        if (p[i].b<p[i].s)
            l[id[p[i].b]+1]=true, cnt[id[p[i].b]+1]++;
            else r[id[p[i].b]]=true, cnt[id[p[i].b]]++;
        p[i].s=id[p[i].s];
    }
    int pl=1, pr=0;
    for (int i=1; i<=num; i++)
        if (cnt[i]==0) q[++pr]=i;
    while (pl<=pr){
        int x=q[pl++];
        if (x!=1&&l[x]==0){if (--cnt[x-1]==0) q[++pr]=x-1;}
        if (x!=num&&r[x]==0){if (--cnt[x+1]==0) q[++pr]=x+1;}
    }
    for (int i=1; i<=num; i++){
        int x=q[i], flag=true;
        mxl[x]=x, mxr[x]=x;
        while (flag){
            flag=false;
            if (l[mxl[x]]==true&&mxl[x]<=p[mxl[x]-1].s&&p[mxl[x]-1].s<=mxr[x]) 
                mxl[x]=mxl[mxl[x]-1], flag=true;
            if (r[mxr[x]]==true&&mxl[x]<=p[mxr[x]].s&&p[mxr[x]].s<=mxr[x]) 
                mxr[x]=mxr[mxr[x]+1], flag=true;
        }
    }
    for (int i=1; i<=tmp; i++){
        int u=id[read()], v=id[read()];
        if (mxl[u]<=v&&v<=mxr[u])
            printf("YES\n");
            else printf("NO\n");
    }
    return 0;
}