CDOJ 1071 秋实大哥下棋线段树

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

分析：运用扫描线，先从左到右扫描，用纵坐标进行建树，

随着扫描线的右向右移动。不断更新横坐标小于扫描线的车

更新的时候在树中更新车的纵坐标的位置，把该位置的值变成该车的横坐标

线段树维护的是区间最大值和最小值

这样每到一个矩形区域的右边界，查询该区间的纵坐标区间内的最大值和最小值

如果最大值小于右边界，最小值大于左边界

那么这个矩形区域内每一行都可以被矩形区域内的车覆盖，标记一下

同理，从下到上扫描，可以找到符合条件的矩形

#include<cstdio>

#include<cstring>

#include<queue>

#include<cstdlib>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

typedef long long LL;

const int N=2e5+;

int n,m,k,q;

struct Rec

{

    int x1,x2,y1,y2,id;

    bool operator<(const Rec &e)const

    {

        return x2<e.x2;

    }

} o[N];

bool cmp1(Rec a,Rec b)

{

    return a.x2<b.x2;

}

bool cmp2(Rec a,Rec b)

{

    return a.y2<b.y2;

}

struct Point

{

    int x,y;

} p[N];

bool cmp3(Point a,Point b)

{

    return a.x<b.x;

}

bool cmp4(Point a,Point b)

{

    return a.y<b.y;

}

int c[N<<],b[N<<];

void build(int rt,int l,int r)

{

    b[rt]=c[rt]=N;

    if(l==r)return;

    int mid=(l+r)>>;

    build(rt*,l,mid);

    build(rt*+,mid+,r);

}

void pushup(int rt)

{

    c[rt]=min(c[rt*],c[rt*+]);

    b[rt]=max(b[rt*],b[rt*+]);

}

void update(int rt,int l,int r,int pos,int t)

{

    if(l==r)

    {

        b[rt]=c[rt]=t;

        return;

    }

    int mid=(l+r)>>;

    if(pos<=mid)update(rt*,l,mid,pos,t);

    else update(rt*+,mid+,r,pos,t);

    pushup(rt);

}

int querymin(int rt,int l,int r,int x,int y)

{

    if(x<=l&&r<=y)

        return c[rt];

    int res=N;

    int mid=(l+r)>>;

    if(x<=mid)res=min(res,querymin(rt*,l,mid,x,y));

    if(y>mid)res=min(res,querymin(rt*+,mid+,r,x,y));

    return res;

}

int querymax(int rt,int l,int r,int x,int y)

{

    if(x<=l&&r<=y)

        return b[rt];

    int res=-;

    int mid=(l+r)>>;

    if(x<=mid)res=max(res,querymax(rt*,l,mid,x,y));

    if(y>mid) res=max(res,querymax(rt*+,mid+,r,x,y));

    return res;

}

bool ans[N];

int main()

{

    scanf("%d%d%d%d",&n,&m,&k,&q);

    for(int i=; i<=k; ++i)

        scanf("%d%d",&p[i].x,&p[i].y);

    for(int i=; i<=q; ++i)

        scanf("%d%d%d%d",&o[i].x1,&o[i].y1,&o[i].x2,&o[i].y2),o[i].id=i;

    sort(p+,p++k,cmp3);

    sort(o+,o++q,cmp1);

    int cnt=;

    build(,,m);

    for(int i=; i<=q; ++i)

    {

        for(; cnt<=k&&p[cnt].x<=o[i].x2; ++cnt)

            update(,,m,p[cnt].y,p[cnt].x);

        int a1=querymin(,,m,o[i].y1,o[i].y2);

        int a2=querymax(,,m,o[i].y1,o[i].y2);

        if(a1>=o[i].x1&&a2<=o[i].x2)

            ans[o[i].id]=;

    }

    sort(p+,p+k+,cmp4);

    sort(o+,o++q,cmp2);

    build(,,n),cnt=;

    for(int i=; i<=q; ++i)

    {

        for(; cnt<=k&&p[cnt].y<=o[i].y2; ++cnt)

            update(,,n,p[cnt].x,p[cnt].y);

        int a1=querymin(,,n,o[i].x1,o[i].x2);

        int a2=querymax(,,n,o[i].x1,o[i].x2);

        if(a1>=o[i].y1&&a2<=o[i].y2)

            ans[o[i].id]=;

    }

    for(int i=; i<=q; ++i)

        if(ans[i])printf("YES\n");

        else printf("NO\n");

    return ;

}