POJ 3667 Hotel

刚开始是照着小媛姐的代码来写的，因为感觉自己对细节的处理认识不是很深刻。。

但是小媛姐把懒惰标记作为区间是否被0/1覆盖来做的，

也就是说懒惰标记会被pushup

于是A掉了以后打算用不pushup懒惰标记的方法写，

写了一下午= =。。。

于是乎总结了下懒惰标记和区间是否被覆盖的区别。。

第一个区别是区间被覆盖的标记需要pushup，而懒惰标记在pushdown的时候需要赋值为-1；

第二个区别就是在update的时候，如果需要懒惰标记来计算节点的值的时候，懒惰标记是不能用来计算的，

改进的方法就是通过l,r来判断。。

从褚神那得知#define 是可以替代含有空格串的，于是乎#define canshu int l,int r,int rt....

这是区间覆盖的标记的代码：

[cpp]
#include<stdio.h>
#define ls rt*2
#define rs rt*2+1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define canshu int l,int r,int rt
#define X 50010
int tr[X*4],lv[X*4],rv[X*4],sum[X*4];
void tclear(int rt,int s){
    sum[rt]=lv[rt]=rv[rt]=s;
}
void build(canshu){
    tr[rt]=0;
    tclear(rt,r-l+1);
    if(l==r)return ;
    int mid=l+r>>1;
    build(lson);
    build(rson);
}
int max(int a,int b,int c){
    if(a>=b&&a>=c)return a;
    if(b>=a&&b>=c)return b;
    if(c>=a&&c>=b)return c;
}
void pushup(int rt){
    tr[rt]=tr[ls]==tr[rs]?tr[ls]:-1;
    lv[rt]=lv[ls]+(tr[ls]==0?lv[rs]:0);
    rv[rt]=rv[rs]+(tr[rs]==0?rv[ls]:0);
    sum[rt]=max(sum[ls],sum[rs],rv[ls]+lv[rs]);
}
void pushdown(canshu){
    if(tr[rt]!=-1){
        int mid=l+r>>1;
        tr[ls]=tr[rs]=tr[rt];
        tclear(ls,(!tr[rt])*(mid-l+1));
        tclear(rs,(!tr[rt])*(r-mid));
    }
}
int ll,rr,c;
void update(canshu){
    if(ll<=l&&rr>=r){
        tr[rt]=c;
        tclear(rt,(!c)*(r-l+1));
        //printf("updt: l=%d r=%d flag=%d sum=%d lv=%d rv=%d\n",l,r,tr[rt],sum[rt],lv[rt],rv[rt]);
        return ;
    }
    pushdown(l,r,rt);
    int mid=l+r>>1;
    if(ll<=mid)update(lson);
    if(rr> mid)update(rson);
    pushup(rt);
    //rintf("updt: l=%d r=%d flag=%d sum=%d lv=%d rv=%d\n",l,r,tr[rt],sum[rt],lv[rt],rv[rt]);
}
int que(canshu){
    //printf("que: l=%d r=%d flag=%d sum=%d lv=%d rv=%d\n",l,r,tr[rt],sum[rt],lv[rt],rv[rt]);
    if(tr[rt]==0){
        if(sum[rt]>=c)return l;
        return -1;
    }
    if(tr[rt]==1)return -1;
    pushdown(l,r,rt);
    int mid=l+r>>1;
    if(sum[ls]>=c)return que(lson);
    else if(rv[ls]+lv[rs]>=c)
        return mid-rv[ls]+1;
    else if(sum[rs]>=c)return que(rson);
    return -1;
}
int main(){
    freopen("hotel.2.in","r",stdin);
    freopen("out2.txt","w",stdout);
    int f,pos,d,n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--){
        scanf("%d",&f);
        if(f==1){
            scanf("%d",&c);
            pos=que(1,n,1);
            if(pos==-1){printf("0\n");continue;}
            ll=pos;rr=pos+c-1;c=1;
            update(1,n,1);
            printf("%d\n",pos);
        }
        else {
            scanf("%d%d",&pos,&c);
            ll=pos;rr=pos+c-1;c=0;
            update(1,n,1);
        }
    }
    return 0;
}

#include<stdio.h>
#define ls rt*2
#define rs rt*2+1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define canshu int l,int r,int rt
#define X 50010
int tr[X*4],lv[X*4],rv[X*4],sum[X*4];
void tclear(int rt,int s){
    sum[rt]=lv[rt]=rv[rt]=s;
}
void build(canshu){
    tr[rt]=0;
    tclear(rt,r-l+1);
    if(l==r)return ;
    int mid=l+r>>1;
    build(lson);
    build(rson);
}
int max(int a,int b,int c){
    if(a>=b&&a>=c)return a;
    if(b>=a&&b>=c)return b;
    if(c>=a&&c>=b)return c;
}
void pushup(int rt){
    tr[rt]=tr[ls]==tr[rs]?tr[ls]:-1;
    lv[rt]=lv[ls]+(tr[ls]==0?lv[rs]:0);
    rv[rt]=rv[rs]+(tr[rs]==0?rv[ls]:0);
    sum[rt]=max(sum[ls],sum[rs],rv[ls]+lv[rs]);
}
void pushdown(canshu){
    if(tr[rt]!=-1){
        int mid=l+r>>1;
        tr[ls]=tr[rs]=tr[rt];
        tclear(ls,(!tr[rt])*(mid-l+1));
        tclear(rs,(!tr[rt])*(r-mid));
    }
}
int ll,rr,c;
void update(canshu){
    if(ll<=l&&rr>=r){
        tr[rt]=c;
        tclear(rt,(!c)*(r-l+1));
        //printf("updt: l=%d r=%d&

补充：软件开发 , C++ ,