bzoj5048: 塌陷的牧场

Description

农夫小Q将他的奶牛们饲养在一个长n宽m的矩形网格牧场中。行从上到下依次编号为1到n，列从左往右依次编号为1

到m。为了防止奶牛们逃跑，小Q在牧场外圈安装了一排电网，只要奶牛走出这个n*m的矩形，就会触电死去。在牧

场中，有e个格子塌陷了，一旦奶牛踩在上面，就会掉下去摔死。小Q为了饲养尽可能多的奶牛，在每个没有塌陷的

格子上，都饲养着一头奶牛。tangjz偷走了小Q的口哨，并用口哨向奶牛们依次施放了q条指令，每条指令包含两个

参数d和k，d表示上下左右之一的方向，k表示前进步数。发出指令后，每头奶牛都会听话地执行指令，甚至会因此

丧生。所有奶牛移动完毕之后，tangjz才会施放下一条指令。请写一个程序统计每条指令中小Q损失了多少头奶牛

Input

第一行包含4个正整数n,m,e,q(1<=n,m,q<=2000,0<=e<=min(nm,2000))

分别表示牧场的长宽、塌陷的格子数以及指令数。

接下来e行，每行两个正整数x_i,y_i(1<=x_i<=n,1<=y_i<=m)

表示每个塌陷格子的坐标。输入数据保证每个格子不会被描述多次。

接下来q行，每行包含一个字符d和一个正整数k(1<=k<=2000)

描述每条指令。其中UDLR分别表示上下左右。

Output

输出q行，每行一个整数，即第i条指令中损失的奶牛数量。

塌陷的格子数和询问数都很少，可以反过来移动这些格子来计算每次新覆盖了多少位置，查询区间内未被覆盖的位置可以用zkw线段树实现，时间复杂度O(qelog(n+m)+nm)。

#include<bits/stdc++.h>

const int N=;

int n,m,e,q,mx;

int xs[N],ys[N],dc=,tr[][N][N*],ds[N*N],dp=,*t,Q[N];

bool dd[N][N];

void del(int x,int y){

    if(!dd[x][y])dd[x][y]=,++dc;

}

void chk(int*t,int x){

    for(int w=x;w>&&!t[w^];t[w>>=]=);

    int ql=,qr=;

    t[x]=,Q[++qr]=x;

    while(ql!=qr){

        int w=Q[++ql];

        if(w>=mx)ds[dp++]=w-mx;

        else{

            w<<=;

            if(t[w])t[w]=,Q[++qr]=w;

            ++w;

            if(t[w])t[w]=,Q[++qr]=w;

        }

    }

}

void dt(int*t,int l,int r){

    for(l+=mx-,r+=mx+;r-l!=;l>>=,r>>=){

        if(~l&&&t[l+])chk(t,l+);

        if(r&&&t[r-])chk(t,r-);

    }

}

void dlr(int x,int l,int r){

    if(x<||x>n)return;

    if(r>m)r=m;if(l<)l=;

    if(l<=r)dt(tr[][x],l,r);

    for(;dp;del(x,ds[--dp]));

}

void dud(int y,int l,int r){

    if(y<||y>m)return;

    if(r>n)r=n;if(l<)l=;

    if(l<=r)dt(tr[][y],l,r);

    for(;dp;del(ds[--dp],y));

}

void init(int*t,int c){

    for(int i=;i<=c;++i)t[mx+i]=;

    for(int i=mx-;i;--i)t[i]=t[i<<]|t[(i<<)+];

}

int main(){

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

    for(mx=;mx<=std::max(n,m)+;mx<<=);

    for(int i=;i<=e;++i)scanf("%d%d",xs+i,ys+i),del(xs[i],ys[i]);

    for(int i=;i<=n;++i)init(tr[][i],m);

    for(int i=;i<=m;++i)init(tr[][i],n);

    int lp=,rp=m+,up=,dp=n+;

    while(q--){

        char dir;

        int d,v0=dc;

        scanf(" %c%d",&dir,&d);

        if(dir=='R'){//m-

            for(int i=;i<=e;++i)dlr(xs[i],ys[i]-d,ys[i]),ys[i]-=d;

            for(int i=;i<=n;++i)dlr(i,rp-d,rp);

            lp-=d,rp-=d;

        }

        if(dir=='L'){//m+

            for(int i=;i<=e;++i)dlr(xs[i],ys[i],ys[i]+d),ys[i]+=d;

            for(int i=;i<=n;++i)dlr(i,lp,lp+d);

            lp+=d,rp+=d;

        }

        if(dir=='D'){//n-

            for(int i=;i<=e;++i)dud(ys[i],xs[i]-d,xs[i]),xs[i]-=d;

            for(int i=;i<=m;++i)dud(i,dp-d,dp);

            up-=d,dp-=d;

        }

        if(dir=='U'){//n+

            for(int i=;i<=e;++i)dud(ys[i],xs[i],xs[i]+d),xs[i]+=d;

            for(int i=;i<=m;++i)dud(i,up,up+d);

            up+=d,dp+=d;

        }

        printf("%d\n",dc-v0);

    }

    return ;

}