BZOJ 1593[Usaco2008 Feb]Hotel 旅馆

参考样例，第一行输入n，m ，n代表有n个房间，编号为1—n，开始都为空房，m表示以下有m行操作，以下 每行先输入一个数 i ，表示一种操作：

若i为1，表示查询房间，再输入一个数x，表示在1–n 房间中找到长度为x的连续空房，输出连续x个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为x的连续空房，输出0。

若i为2，表示退房，再输入两个数 x，y 代表 房间号 x—x+y-1 退房，即让房间为空。

线段树代码题

维护区间最左面的连续1的长度，最右边连续1的长度，以及区间内连续1最长的长度

线段树维护左边和右边是为了为父节点合并
(上传) 做铺垫

然后 就是查找的时候需要自己想想

如果当前区间的左儿子中有连续x的1，就返回左儿子的答案

如果左儿子最右边连续的与右儿子最左边连续之和大于x，就返回答案减去左儿子的大小+mid+1(满足尽量靠左)

如果还不行就查右儿子

再不行返回0

CODE：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
const int N = 100110;
int sum[N<<2],cov[N<<2];
int ls[N<<2],rs[N<<2],mx[N<<2];//全空为1 
inline int pushup(int cur,int x){
    sum[cur]=sum[cur<<1]+sum[cur<<1|1]; 
    if(sum[cur<<1]==(x+1>>1)) ls[cur]=sum[cur<<1]+ls[cur<<1|1];
    else ls[cur]=ls[cur<<1];
    if(sum[cur<<1|1]==(x>>1)) rs[cur]=sum[cur<<1|1]+rs[cur<<1];
    else rs[cur]=rs[cur<<1|1];
    mx[cur]=std::max(mx[cur<<1],std::max(mx[cur<<1|1],ls[cur<<1|1]+rs[cur<<1]));
}
inline int pushdown(int cur,int x){
    if(cov[cur]!=-1){
        sum[cur<<1]=cov[cur]*(x+1>>1);
        sum[cur<<1|1]=cov[cur]*(x>>1);
        cov[cur<<1]=cov[cur];
        cov[cur<<1|1]=cov[cur];
        cov[cur]=-1;
        if(sum[cur<<1]) mx[cur<<1]=ls[cur<<1]=rs[cur<<1]=(x+1)>>1;
        else mx[cur<<1]=ls[cur<<1]=rs[cur<<1]=0;
        if(sum[cur<<1|1]) mx[cur<<1|1]=ls[cur<<1|1]=rs[cur<<1|1]=x>>1;
        else mx[cur<<1|1]=ls[cur<<1|1]=rs[cur<<1|1]=0;
    }
}
inline int build(int l,int r,int cur){
    cov[cur]=-1;
    if(l==r){
        sum[cur]=ls[cur]=rs[cur]=mx[cur]=1;

        return 0;
    }
    int mid=l+r>>1;
    build(l,mid,cur<<1);
    build(mid+1,r,cur<<1|1);
    pushup(cur,r-l+1);
    return 0;
}
inline int ask(int l,int r,int cur,int x){
    pushdown(cur,r-l+1);
    int mid=l+r>>1;

    if(l==r){
        if(sum[cur]==0) return 0;
        return 1;
    }
    if(mx[cur<<1]>=x) return ask(l,mid,cur<<1,x);
    if(rs[cur<<1]+ls[cur<<1|1]>=x){
        return mid-rs[cur<<1]+1;
    }
    if(mx[cur<<1|1]>=x)return ask(mid+1,r,cur<<1|1,x);
    else return 0;
}
inline int change(int l,int r,int L,int R,int cur,int x){
    if(L<=l&&r<=R){
        sum[cur]=rs[cur]=ls[cur]=mx[cur]=x*(r-l+1);
        cov[cur]=x;
        return 0;
    }
    pushdown(cur,r-l+1);
    int mid = l+r>>1;
    if(L<=mid) change(l,mid,L,R,cur<<1,x);
    if(R>mid) change(mid+1,r,L,R,cur<<1|1,x);
    pushup(cur,r-l+1);
    return 0;
}
int n,m;
int main (){
    scanf("%d %d",&n,&m);
    build(1,n,1);
    while(m--){
        int od,l,r,x;
        scanf("%d",&od);
        if(od==1){
            scanf("%d",&x);
            int s=ask(1,n,1,x);

            printf("%d\n",s);
            if(s==0) continue;
            change(1,n,s,s+x-1,1,0);

        }
        if(od==2){
            scanf("%d %d",&l,&r);
            change(1,n,l,l+r-1,1,1);
        }
    }
    return 0;
}