#2508. 「AHOI / HNOI2018」游戏

题目描述

一次小 G 和小 H 在玩寻宝游戏，有 nnn 个房间排成一列，编号为 1,2,…,n，相邻房间之间都有 111 道门。其中一部分门上有锁（因此需要对应的钥匙才能开门），其余的门都能直接打开。

现在小 G 告诉了小 H 每把锁的钥匙在哪个房间里（每把锁有且只有一把钥匙），并作出 ppp 次指示：第 iii 次让小 H 从第 SiS_iSi 个房间出发，去第 TiT_iTi 个房间寻宝。但是小 G 有时会故意在指令里放入死路，而小 H 也不想浪费多余的体力去尝试，于是想事先调查清楚每次的指令是否存在一条通路。

你是否能为小 H 作出解答呢？

输入格式

第一行三个整数nnn，mmm，ppp，代表共有 nnn 个房间，mmm 道门上了锁，以及 ppp 个询问。

接下来 mmm 行每行有两个整数xxx，yyy，代表第 xxx 到第 x+1x + 1x+1 个房间的门上有把锁，并且这把锁的钥匙被放在了第 yyy 个房间里。输入保证 xxx 不重复。

接下来 ppp 行，其中第 iii 行是两个整数 SiS_iSi，TiT_iTi，代表一次询问。

输出格式

输出 mmm 行，每行一个大写的 YES 或 NO 分别代表能或不能到达。

样例

样例输入 1

样例输出 1

YES

NO

YES

YES

NO

样例解释 1

第一个询问 S=2S = 2S=2、T=5T = 5T=5 的一条可行路线是：2→3→2→1→2→3→4→52 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 52→3→2→1→2→3→4→5。

样例输入 2

此组样例满足特性：y≤xy \le xy≤x 恒成立

样例输出 2

YES

YES

NO

NO

样例解释 2

第一个询问 222 和 111 房间之间没有锁所以为一条通路。

数据范围与提示

测试点编号	n	m	其他特性
1	≤1000 \le 1000≤1000	≤1000 \le 1000≤1000	无
2	≤1000 \le 1000≤1000	≤1000 \le 1000≤1000	无
3	≤105 \le 10^5≤105	≤105 \le 10^5≤105	y≤xy \le xy≤x 恒成立
4	≤105 \le 10^5≤105	≤105 \le 10^5≤105	y≤xy \le xy≤x 恒成立
5	≤105 \le 10^5≤105	≤105 \le 10^5≤105	无
6	≤105 \le 10^5≤105	≤105 \le 10^5≤105	无
7	≤106 \le 10^6≤106	≤106 \le 10^6≤106	y≤xy \le xy≤x 恒成立
8	≤106 \le 10^6≤106	≤106 \le 10^6≤106	y≤xy \le xy≤x 恒成立
9	≤106 \le 10^6≤106	≤106 \le 10^6≤106	无
10	≤106 \le 10^6≤106	≤106 \le 10^6≤106	无

对于所有数据，保证 1≤n,p≤1061 \le n,p \le 10^61≤n,p≤106，0≤m<n0 \le m < n0≤m<n，1≤x,y,Si,Ti<n1 \le x, y, S_i,T_i < n1≤x,y,Si,Ti<n，保证 xxx 不重复。

由于本题输入文件较大，建议在程序中使用读入优化。

/*

    一个点能够扩张的区间是由它周围的点转移过来的

    随机化更新的顺序，每次更新进行左右扩张即可

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<algorithm>

#define maxn 1000010

using namespace std;

int n,L[maxn],R[maxn],p[maxn],rd[maxn];

int qread(){

    int i=,j=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}

    while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}

    return i*j;

}

void extend(int i){

    bool flag=;

    while(flag){

        flag=;

        while(L[i]> && (p[L[i]-]==||(L[i]<=p[L[i]-]&&p[L[i]-]<=R[i])))

            flag=,L[i]=min(L[i],L[L[i]-]),R[i]=max(R[i],R[R[i]-]);

        while(R[i]<n && (p[R[i]]==||(L[i]<=p[R[i]]&&p[R[i]]<=R[i])))

            flag=,L[i]=min(L[i],L[L[i]+]),R[i]=max(R[i],R[R[i]+]);

    }

}

int main(){

    srand(time());

    int m,q,x,y;

    n=qread();m=qread();q=qread();

    for(int i=;i<=m;i++){

        x=qread();

        p[x]=qread();

    }

    for(int i=;i<=n;i++)L[i]=R[i]=i;

    for(int i=;i<=n;i++)rd[i]=i;

    random_shuffle(rd+,rd+n+);

    for(int i=;i<=n;i++)extend(rd[i]);

    while(q--){

        x=qread();y=qread();

        if(L[x]<=y&&y<=R[x])puts("YES");

        else puts("NO");

    }

    return ;

}

秒客网

loj #2508. 「AHOI / HNOI2018」游戏