当前位置:编程学习 > C/C++ >>

POJ 3667 线段树 + 延迟标记 + 区间处理

[cpp]  
/* 
 
贴个神牛的代码,自己写的代码难看的别提有多恶心了 ... 
 
类型:线段树 + 延迟标记 + 区间合并...  
 
*/  
#include<iostream>  
#include<cstring>  
#include<cctype>  
#include<cstdio>  
#include<algorithm>  
using namespace std;  
#define L(r) r<<1  
#define R(r) r<<1|1  
const int MAXM=50005;  
typedef struct  
{  
    int lsum,rsum,msum;//分别表示左边最大房间数,右边最大房间数,整体最大房间数  
    int cover;//是否住下  
}node;  
node tree[MAXM<<2];  
void pushDown(int root,int m)//向下更新  
{    www.zzzyk.com
    if(tree[root].cover==-1) return;//是否已经更新  
    tree[L(root)].cover=tree[R(root)].cover=tree[root].cover;  
    tree[L(root)].msum=tree[L(root)].lsum=tree[L(root)].rsum=tree[root].cover?0:m-(m>>1);  
    tree[R(root)].msum=tree[R(root)].lsum=tree[R(root)].rsum=tree[root].cover?0:(m>>1);  
    tree[root].cover=-1;  
}  
void pushUp(int root,int m)//向上更新  
{  
    tree[root].lsum=tree[L(root)].lsum;  
    tree[root].rsum=tree[R(root)].rsum;  
    if(tree[root].lsum==m-(m>>1) ) tree[root].lsum+=tree[R(root)].lsum;  // 区间合并   
    if(tree[root].rsum==(m>>1) ) tree[root].rsum+=tree[L(root)].rsum;     
    tree[root].msum=max(tree[R(root)].lsum+tree[L(root)].rsum,max(tree[L(root)].msum,tree[R(root)].msum) );  
}  
void Create(int l,int r,int root)//建树过程  
{  
    tree[root].cover=-1;  
    tree[root].lsum=tree[root].rsum=tree[root].msum=r-l+1;  
    if(l==r){return;}  
    int mid=(l+r)>>1;  
    Create(l,mid,L(root));  
    Create(mid+1,r,R(root));  
}  
void update(int ll,int rr,int c,int l,int r,int root)//更新  
{  
    if(ll<=l&&r<=rr)//如果找到这个范围就直接赋值返回,不向下继续更新  
    {  
        tree[root].msum=tree[root].lsum=tree[root].rsum=c?0:r-l+1;  
        tree[root].cover=c;  
        return;  
    }  
    pushDown(root,r-l+1);//用到这个节点的子节点的时候就向下更新  
    int m=(l+r)>>1;  
    if(ll<=m) update(ll,rr,c,l,m,L(root));  
    if(m<rr) update(ll,rr,c,m+1,r,R(root));  
    pushUp(root,r-l+1);//向下更新完后需要把节点信息反馈给父节点  
}  
int query(int w,int l,int r,int root)//查询满足连续房间数量的最左节点  
{  
    if(l==r) return l;  
    pushDown(root,r-l+1 );//用到这个节点的子节点的时候就向下更新  
    int m=(l+r)>>1;  
    //////////////////// 注意顺序, 区间的处理   
    if(tree[L(root)].msum>=w) return query(w,l,m,L(root));//如果左儿子满足就询问左儿子  
    else if(tree[L(root)].rsum+tree[R(root)].lsum>=w) return m-tree[L(root)].rsum+1;//如果左儿子和右儿子之间的数量满足,则范围左儿子右边连续房间第一个的编号  
    else return query(w,m+1,r,R(root));//如果两者都不满足则询问右儿子  
}  
int main()  
{  
    int n,m;  
    while(~scanf("%d %d",&n,&m))  
    {  
        Create(1,n,1);  
        int a,num,x,d,p;  
        for(int i=0;i<m;++i)  
        {  
            scanf("%d",&a);  
            if(1==a)  
            {  
                scanf("%d",&num);  
                if(tree[1].msum<num) puts("0");//如果整个区间的最大连续房间数量小于预定的数量就输出0  
                else  
                {  
                    p=query(num,1,n,1);//找到最左节点p  
                    printf("%d\n",p);  
                    update(p,p+num-1,1,1,n,1);//把已经有人的房间标记一下  
                }  
            }  
            else  
            {  
                scanf("%d %d",&x,&d);  
                update(x,x+d-1,0,1,n,1);//把此范围的房间标记成无人  
            }  
        }  
    }  
    return 0;  
}  
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,