POJ3667-Hotel-线段树区间归并(模板)

POJ3667-Hotel-线段树区间合并(模板)

题目链接：http://poj.org/problem?id=3667

线段树真是牛逼啊，这么多的功能。。。

这是个线段树维护区间合并的问题；我们要维护一个区间的从左端点开始的最长区间，右端点的最长区间，以及该区间的最长区间，有了这些信息我们就可以轻易的合并子节点的信息，简单更新了；

好吧，我就不详细介绍了，就贴一个我学习的博客吧，链接：http://blog.****.net/piaoyi0208/article/details/8149804

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<cmath>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#define LL long long
#define inf 1<<30
#define s(a) scanf("%d",&a)
#define Clear(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=50015;
int n,a,m,b;
struct node
{
    int l,r;
    int cover;  //  保存是否住人的信息；用-1,0,1表示；
    int ls,rs,ms;   //  分别表示左端点起最大长度，右端点起最大长度，和整个区间最大长度；
}node[N<<2];
void Push_Up(int l,int r,int rt)    //  想父节点更新；
{
    node[rt].ls=node[rt<<1].ls;
    node[rt].rs=node[rt<<1|1].rs;
    int mid=(l+r)>>1;
    if(node[rt].ls==mid-l+1) node[rt].ls+=node[rt<<1|1].ls;
    if(node[rt].rs==r-mid) node[rt].rs+=node[rt<<1].rs;
    node[rt].ms=max(max(node[rt<<1].ms,node[rt<<1|1].ms),node[rt<<1].rs+node[rt<<1|1].ls);
}
void Push_Down(int rt)
{
    if(node[rt].cover!=-1){     //  不等于-1表示需要向下更新；
        node[rt<<1].cover=node[rt<<1|1].cover=node[rt].cover;
        if(node[rt].cover){     //  如果等于1，说明将区间标记为0，即表示住人；
            node[rt<<1].ls=node[rt<<1].rs=node[rt<<1].ms=0;
            node[rt<<1|1].ls=node[rt<<1|1].rs=node[rt<<1|1].ms=0;
        }else{
            node[rt<<1].ls=node[rt<<1].rs=node[rt<<1].ms=node[rt<<1].r-node[rt<<1].l+1;
            node[rt<<1|1].ls=node[rt<<1|1].rs=node[rt<<1|1].ms=node[rt<<1|1].r-node[rt<<1|1].l+1;
        }
        node[rt].cover=-1;      //  已经向下更新了，清零；
    }
}
void Build(int l,int r,int rt)
{
    node[rt].l=l;
    node[rt].r=r;
    node[rt].cover=-1;
    node[rt].ls=node[rt].rs=node[rt].ms=r-l+1;
    if(l!=r){
        int mid=(l+r)>>1;
        Build(l,mid,rt<<1);
        Build(mid+1,r,rt<<1|1);
    }
}
void Updata(int l,int r,int v,int rt)
{
    int ll=node[rt].l,rr=node[rt].r;
    if(ll==l&&rr==r){
        node[rt].cover=v;
        if(v){
            node[rt].ls=node[rt].rs=node[rt].ms=0;
        }else{
            node[rt].ls=node[rt].rs=node[rt].ms=r-l+1;
        }
        return ;
    }
    Push_Down(rt);
    int mid=(ll+rr)>>1;
    if(r<=mid) Updata(l,r,v,rt<<1);
    else if(l>mid) Updata(l,r,v,rt<<1|1);
    else{
        Updata(l,mid,v,rt<<1);
        Updata(mid+1,r,v,rt<<1|1);
    }
    Push_Up(node[rt].l,node[rt].r,rt);
}
int Query(int l,int r,int v,int rt)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    Push_Down(rt);
    if(node[rt<<1].ms>=v) return Query(l,mid,v,rt<<1);
    else if(node[rt<<1].rs+node[rt<<1|1].ls>=v) return mid-node[rt<<1].rs+1;
    else return Query(mid+1,r,v,rt<<1|1);
}
int main()
{
    //freopen("../../in.txt","r",stdin);
    //freopen("../../out.txt","w",stdout);
    while(~scanf("%d%d",&n,&m)){
        Build(1,n,1);
        for(int i=0;i<m;i++){
            s(a);
            if(a==1){
                s(a);
                if(node[1].ms<a){
                    printf("0\n");
                    continue;
                }else{
                    b=Query(1,n,a,1);
                    printf("%d\n",b);
                    Updata(b,b+a-1,1,1);
                }
            }else{
                s(a); s(b);
                Updata(a,a+b-1,0,1);
            }
        }
    }
    return 0;
}