【BZOJ-4422】Cow Confinement 线段树 + 扫描线 + 差分（优化DP）

2022-11-15 09:53:49

4422: [Cerc2015]Cow Confinement

Time Limit: 50 Sec Memory Limit: 512 MB
Submit: 61 Solved: 26
[Submit][Status][Discuss]

Description

一个10^6行10^6列的网格图，上面有一些牛、花和一些矩形围栏，围栏在格子的边界上，牛和花在格子里，牛只能向下或向右走，牛也不能穿过围栏和地图边界，求每头牛它能到达的花的数量。注意栅栏不会相交

【BZOJ-4422】Cow Confinement 线段树 + 扫描线 + 差分（优化DP）

Input

第一行一个数f表示矩形围栏的数量。

接下来f行，每行四个数x1,y1,x2,y2，表示(x1,y1)在围栏内部矩形的左上角，(x2,y2)在右下角。

接下来一行一个数m表示花的数量。

接下来m行每行两个数x,y，表示在(x,y)处有一朵花。

接下来一行一个数n表示牛的数量。

接下来n行每行两个数x,y，表示在(x,y)处有一头牛。

Output

总共n行，每行一个数ans，第i个数表示第i头牛能到ans个花。

Sample Input

4
2 2 8 4
1 9 4 10
6 7 9 9
3 3 7 3
9
3 4
8 4
11 5
10 7
10 8
9 8
2 8
4 11
9 11
8
1 1
5 10
6 9
3 7
7 1
4 2
7 5
3 3

Sample Output

5
1
0
1
3
1
3
0

HINT

0<=f<=200000

0<=m<=200000

1<=n<=200000

Source

Solution

一道idea非常好的题

首先这题可以DP,不过转移之类的需要讨论，比较麻烦

$dp[i][j]=\begin{Bmatrix} 0(下面和右面都有栅栏)\\ dp[i+1][j](右面有栅栏)\\ dp[i][j+1](下面有栅栏)\\ dp[i+1][j]+dp[i][j+1]-dp[i+1][j+1]((i+1,j+1)不是栅栏的左上角)\\ dp[i+1][j]+dp[i][j+1]-dp[x+1][y+1]((i+1,j+1)是左上角,(x,y)是右下角)& & \end{Bmatrix}+flower[i][j]$

这样DP的时间复杂度是$O((N+F+M)^{2})$的

那么考虑优化这个DP

差分出$f[i][j]$表示$(i,j)$能得到，但$(i,j-1)$不能得到的花的数量

那么考虑扫描线，从右往左

那讨论一下各种情况，

遇到花单点数值+1；遇到一个未出现过的栅栏，区间查询和，单点修改数值，区间修改覆盖0；删除一个栅栏，区间修改覆盖0；遇见一头牛，找到下方第一个栅栏，区间求和；

显然都可以用线段树维护

查找下方第一个栅栏？维护一个最小即可

时间复杂度是$O(10^{6}log10^{6})$

实现起来有一些细节，线段树中需要加特判，当所需要修改的坐标为0啊之类的

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

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

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

    return x*f;

}

#define MAXY 1000000

#define MAXF 200010

#define MAXN 200010

#define MAXM 200010

int F,M,N;

struct FenceNode{int x1,x2,y1,y2;}fen[MAXF];

struct CowNode{int x,y,id;}cow[MAXN];

struct FlowerNode{int x,y;}flo[MAXM];

struct LineNode{int y,x1,x2,id,f;}line[MAXF<<];  int tp;

struct SegmentTreeNode{int l,r,tag,bk,sum;}tree[MAXY<<];

int tmp[MAXF],ans[MAXN];

inline void Update(int now)

{

    tree[now].bk=min(tree[now<<].bk,tree[now<<|].bk);

    tree[now].sum=tree[now<<].sum+tree[now<<|].sum;

}

inline void PushDown(int now)

{

    if (!tree[now].tag || tree[now].l==tree[now].r) return;

    tree[now].tag=;

    tree[now<<].sum=; tree[now<<|].sum=;

    tree[now<<].tag=; tree[now<<|].tag=;

}

inline void BuildTree(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r;

    tree[now].sum=; tree[now].tag=; tree[now].bk=MAXY;

    if (l==r) return;

    int mid=(l+r)>>;

    BuildTree(now<<,l,mid);

    BuildTree(now<<|,mid+,r);

    Update(now);

}

inline void PointChangeSum(int now,int pos,int D)

{

    if (pos==MAXY+ || pos==) return;

    int l=tree[now].l,r=tree[now].r;

    PushDown(now);

    if (l==r) {tree[now].sum+=D; return;}

    int mid=(l+r)>>;

    if (pos<=mid) PointChangeSum(now<<,pos,D);

    if (pos>mid) PointChangeSum(now<<|,pos,D);

    Update(now);

}

inline void PointChangeBreak(int now,int pos,int D)

{

    if (pos==MAXY+ || pos==) return;

    int l=tree[now].l,r=tree[now].r;

    PushDown(now);

    if (l==r) {tree[now].bk=D? l:MAXY; return;}

    int mid=(l+r)>>;

    if (pos<=mid) PointChangeBreak(now<<,pos,D);

    if (pos>mid) PointChangeBreak(now<<|,pos,D);

    Update(now);

}

inline void IntervalChange(int now,int L,int R)

{

    if (L== || R==MAXY+ || R<L) return;

    int l=tree[now].l,r=tree[now].r;

    PushDown(now);

    if (L<=l && R>=r) {tree[now].tag=; tree[now].sum=; return;}

    int mid=(l+r)>>;

    if (L<=mid) IntervalChange(now<<,L,R);

    if (R>mid) IntervalChange(now<<|,L,R);

    Update(now);

}

inline int IntervalQuerySum(int now,int L,int R)

{

    if (L== || R==MAXY+ || R<L) return ;

    int l=tree[now].l,r=tree[now].r;

    PushDown(now);

    if (L<=l && R>=r) return tree[now].sum;

    int mid=(l+r)>>,re=;

    if (L<=mid) re+=IntervalQuerySum(now<<,L,R);

    if (R>mid) re+=IntervalQuerySum(now<<|,L,R);

    return re;

}

inline int IntervalQueryBreak(int now,int L,int R)

{

    if (L== || R==MAXY+ || R<L) return ;

    int l=tree[now].l,r=tree[now].r;

    PushDown(now);

    if (L<=l && R>=r) return tree[now].bk;

    int mid=(l+r)>>,re=MAXY;

    if (L<=mid) re=min(re,IntervalQueryBreak(now<<,L,R));

    if (R>mid) re=min(re,IntervalQueryBreak(now<<|,L,R));

    return re;

}

inline bool cmpLine(LineNode A,LineNode B) {return A.y!=B.y? A.y>B.y : A.x1<B.x1;}

inline bool cmpCow(CowNode A,CowNode B) {return A.y>B.y;}

inline bool cmpFlower(FlowerNode A,FlowerNode B) {return A.y>B.y;}

int main()

{

    F=read();

    for (int i=; i<=F; i++) fen[i].x1=read(),fen[i].y1=read(),fen[i].x2=read(),fen[i].y2=read();

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

        line[++tp]=(LineNode){fen[i].y1-,fen[i].x1,fen[i].x2,i,-},

        line[++tp]=(LineNode){fen[i].y2,fen[i].x1,fen[i].x2,i,};

    sort(line+,line+tp+,cmpLine);

    M=read();

    for (int i=; i<=M; i++) flo[i].x=read(),flo[i].y=read();

    sort(flo+,flo+M+,cmpFlower);

    N=read();

    for (int i=; i<=N; i++) cow[i].x=read(),cow[i].y=read(),cow[i].id=i;

    sort(cow+,cow+N+,cmpCow);

    BuildTree(,,MAXY);

    int nowl=,nowf=,nowc=,next,sum;

    for (int i=MAXY; i; i--)

        {

            while (line[nowl].y==i)

                {

                    if (line[nowl].f==-)

                        {

                            IntervalChange(,line[nowl].x1,line[nowl].x2);

                            PointChangeSum(,line[nowl].x1-,-tmp[line[nowl].id]);

                            PointChangeBreak(,line[nowl].x1-,);

                            PointChangeBreak(,line[nowl].x2,);

                        }

                    else

                        {

                            next=IntervalQueryBreak(,line[nowl].x2,MAXY);

                            sum=IntervalQuerySum(,line[nowl].x1,line[nowl].x2);

                            tmp[line[nowl].id]=IntervalQuerySum(,line[nowl].x2+,next);

                            IntervalChange(,line[nowl].x1,line[nowl].x2);

                            PointChangeSum(,line[nowl].x1-,sum+tmp[line[nowl].id]);

                            PointChangeBreak(,line[nowl].x1-,);

                            PointChangeBreak(,line[nowl].x2,);

                        }

                    nowl++;

                }

            while (flo[nowf].y==i)

                PointChangeSum(,flo[nowf].x,),nowf++;

            while (cow[nowc].y==i)

                next=IntervalQueryBreak(,cow[nowc].x,MAXY),

                ans[cow[nowc].id]=IntervalQuerySum(,cow[nowc].x,next),

                nowc++;

        }

    for (int i=; i<=N; i++) printf("%d\n",ans[i]);

    return ;

}

#include<cstdio>

#include<iostream>

using namespace std;

#include<cstring>

#include<cmath>

#include<algorithm>

const int X=1e6+,Y=1e6,F=2e5+,M=2e5+,N=2e5+;

char * cp=(char *)malloc();

void in(int &x){

    while(*cp<''||*cp>'')++cp;

    for(x=;*cp>=''&&*cp<='';)x=x*+(*cp++^'');

}

struct FenS{

    int xl,xr;

    int y;

    int i;

    bool flag;

    bool operator < (const FenS & o)const{

        return y!=o.y?y>o.y:xl<o.xl;

    }

}fence[F<<];

int fsum[F];

struct FloS{

    int x,y;

    bool operator < (const FloS & o)const{

        return y>o.y;

    }

}flower[M];

struct CS{

    int x,y;

    int i;

    bool operator < (const CS & o)const{

        return y>o.y;

    }

}cow[N];

int ans[N];

struct SS{

    int cnt;

    bool cover;

    bool barrier;

}segt[X<<];

#define lson node<<1,l,l+r>>1

#define rson node<<1|1,(l+r>>1)+1,r

void out(int node,int l,int r){

    printf("segt[%d][%d,%d]={cnt=%d,cover=%d,barrier=%d}\n",node,l,r,segt[node].cnt,segt[node].cover,segt[node].barrier);

}

void pushup(int node){

    segt[node].cnt=segt[node<<].cnt+segt[node<<|].cnt;

    segt[node].barrier=segt[node<<].barrier|segt[node<<|].barrier;

}

void paint(int node){

    //printf("paint(%d)\n",node);

    segt[node].cover=;

    segt[node].cnt=;

}

void pushdown(int node){

    if(segt[node].cover){

        paint(node<<),paint(node<<|);

        segt[node].cover=;

    }

}

void add(int node,int l,int r,int x,int delta){

    //printf("add(%d,%d,%d,%d,%d)\n",node,l,r,x,delta);

    //out(node,l,r);

    segt[node].cnt+=delta;

    if(l!=r){

        pushdown(node);

        if(x<=l+r>>)add(lson,x,delta);

        else add(rson,x,delta);

        pushup(node);

    }

    //printf("add:");

    //out(node,l,r);

}

void cover(int node,int l,int r,int L,int R){

    //out(node,l,r);

    if(L<=l&&r<=R)paint(node);

    else{

        pushdown(node);

        if(L<=l+r>>)cover(lson,L,R);

        if(R>l+r>>)cover(rson,L,R);

        pushup(node);

    }

}

int query_cnt(int node,int l,int r,int L,int R){

    //printf("query(%d,%d,%d,%d,%d)\n",node,l,r,L,R);

    if(L<=l&&r<=R){

        //printf("query_cnt get [%d][%d,%d]=%d\n",node,l,r,segt[node].cnt);

        return segt[node].cnt;

    }

    else{

        pushdown(node);

        int ans=;

        if(L<=l+r>>)ans+=query_cnt(lson,L,R);

        if(R>l+r>>)ans+=query_cnt(rson,L,R);

        return ans;

    }

}

void update(int node,int l,int r,int x){

    if(l==r)segt[node].barrier^=;

    else{

        pushdown(node);

        if(x<=l+r>>)update(lson,x);

        else update(rson,x);

        pushup(node);

    }

    //printf("update:");

    //out(node,l,r);

}

int query_barrier(int node,int l,int r,int L){

    if(l>=L){

        //printf("Query_barrier Get ");

        //out(node,l,r);

        if(segt[node].barrier){

            while(l!=r)

                if(segt[node<<].barrier)node<<=,r=l+r>>;

                else node=node<<|,l=(l+r>>)+;

            return l;

        }

        else return ;

    }

    else{

        int tmp;

        pushdown(node);

        if(L<=l+r>>&&(tmp=query_barrier(lson,L)))return tmp;

        else return query_barrier(rson,L);

    }

}

int main(){

    freopen("cow.in","r",stdin);

    freopen("cow.out","w",stdout);

    fread(cp,,,stdin);

    int f;

    in(f);

    int x1,y1,x2,y2;

    for(int i=f;i--;){

        in(x1),in(y1),in(x2),in(y2);

        fence[i<<]=(FenS){x1,x2,y1-,i,};

        fence[i<<|]=(FenS){x1,x2,y2,i,};

    }

    sort(fence,fence+(f<<));

    int m;

    in(m);

    for(int i=m;i--;)in(flower[i].x),in(flower[i].y);

    sort(flower,flower+m);

    int n;

    in(n);

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

        in(cow[i].x),in(cow[i].y);

        cow[i].i=i;

    }

    sort(cow,cow+n);

    f=m=n=;

    update(,,Y,Y);

    int sum,br;

    for(int i=Y;i;--i){

        //printf("----%d----\n",i);

        for(;fence[f].y==i;++f)

            if(fence[f].flag==){

                cover(,,Y,fence[f].xl,fence[f].xr);

                if(fence[f].xl!=)add(,,Y,fence[f].xl-,-fsum[fence[f].i]);

                if(fence[f].xl!=)update(,,Y,fence[f].xl-);

                if(fence[f].xr!=Y)update(,,Y,fence[f].xr);

            }

            else{

                br=query_barrier(,,Y,fence[f].xr);

                sum=query_cnt(,,Y,fence[f].xl,fence[f].xr);

                fsum[fence[f].i]=query_cnt(,,Y,fence[f].xr+,br);

                cover(,,Y,fence[f].xl,fence[f].xr);

                if(fence[f].xl>)add(,,Y,fence[f].xl-,sum+fsum[fence[f].i]);

                if(fence[f].xl!=)update(,,Y,fence[f].xl-);

                if(fence[f].xr!=Y)update(,,Y,fence[f].xr);

            }

        for(;flower[m].y==i;++m){

            //cout<<flower[m].x<<","<<flower[m].y<<endl;

            add(,,Y,flower[m].x,);

        }

        for(;cow[n].y==i;++n){

            br=query_barrier(,,Y,cow[n].x);

            //printf("br(%d)=%d\n",cow[n].x,br);

            ans[cow[n].i]=query_cnt(,,Y,cow[n].x,br);

            //printf("query(%d,%d)=%d\n",cow[n].x,br,ans[cow[n].i]);

        }

    }

    for(int i=;i<n;++i)printf("%d\n",ans[i]);

}

TA爷的代码

TA爷的模拟赛.....暴力都没写.....有点对不起TA爷....（不过似乎当时这题没得分的？）

自己的代码比较丑，这里附上当时TA爷的std，供参考

码农公寓