M_sea

洛谷4436 [HNOI2018]游戏
LuoguBZOJ分析考虑$20$分的暴力怎么写。预处理出每个点最远能扩展到的左右边界,然后每个询问直接判断即可。...
扫描右侧二维码阅读全文
28
2019/02

洛谷4436 [HNOI2018]游戏

Luogu

BZOJ

分析

考虑$20$分的暴力怎么写。

预处理出每个点最远能扩展到的左右边界,然后每个询问直接判断即可。

发现扩展次数应该不会太多,期望大概在$\log$级别。

于是按照随机顺序去扩展点,就能过了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,m,q;
int a[N],b[N],L[N],R[N];

inline void expand(int x) {
    int l=x,r=x;
    while (233) {
        int flag=0;
        if (l>1&&((l<=a[l-1]&&a[l-1]<=r)||!a[l-1]))
            flag=1,--l,l=min(l,L[l]),r=max(r,R[l]);
        if (r<n&&((l<=a[r]&&a[r]<=r)||!a[r]))
            flag=1,++r,l=min(l,L[r]),r=max(r,R[r]);
        if (!flag) break;
    }
    L[x]=l,R[x]=r;
}

int main() {
    n=read(),m=read(),q=read();
    for (re int i=1;i<=m;++i) {
        int x=read(),y=read();
        a[x]=y;
    }
    for (re int i=1;i<=n;++i) L[i]=n+1,R[i]=0,b[i]=i;
    random_shuffle(b+1,b+n+1);
    for (re int i=1;i<=n;++i) expand(b[i]);
    while (q--) {
        int x=read(),y=read();
        if (L[x]<=y&&y<=R[x]) puts("YES");
        else puts("NO");
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 04 PM

发表评论