经典的线段树应用,寻找最左的k个连续的空房间, 批量入住, 批量退房.

需要保存每个节点的lv(最大左连续数), rv(最大右连续数), cv(最大连续数), col(颜色, lazy-tag用, 0为空, 1为满, -1为混合).

查询时利用lv,cv,rv, 先看左子树, 再看中间, 再看右子树, 反正就这三种情况. 查子区间前down下去col.

更新时批量改变区间的col, 需要更新子区间的话, 先down下去col, 更新完子区间再up上来lv,rv,cv.

ref: http://hi.baidu.com/legend_ni/blog/item/4d757b2ca91da9ece6cd40c2.html

#include<cstdlib>

int inline max(int a,int b) {return a>b?a:b;}
#define MAX 100000
#define lcd root<<1
#define rcd root<<1|1
struct Node 
{
    int l,r,lv,cv,rv,col;//col -1:mix 0:empty 1:full
    int len(){return r-l+1;}
    int mid(){return (l+r)>>1;}
    void doit(){lv=cv=rv=col?0:len();}//if empty or full, update lv,cv,rv
} 
tree[MAX<<2];

void build(int root,int l,int r)
{
    tree[root].l=l; tree[root].r=r;
    tree[root].col=-1;
    tree[root].lv=tree[root].cv=tree[root].rv=tree[root].len();
    if(l==r) return;
    int m=(l+r)>>1;
    build(lcd,l ,m);
    build(rcd,m+1,r);
}

void down(int root)
{
    if(tree[root].len()==1 || tree[root].col==-1) return;
    tree[lcd].col=tree[rcd].col=tree[root].col;
    tree[root].col=-1;
    tree[lcd].doit(); tree[rcd].doit();
}

void up(int root)
{
    tree[root].cv=max(tree[lcd].rv+tree[rcd].lv,
            max(tree[lcd].cv,tree[rcd].cv));
    tree[root].lv=(tree[lcd].cv==tree[lcd].len())?
        tree[lcd].len()+tree[rcd].lv:tree[lcd].lv;
    tree[root].rv=(tree[rcd].cv==tree[rcd].len())?
        tree[rcd].len()+tree[lcd].rv:tree[rcd].rv;
}

int query(int root,int k)
{
    if(tree[root].len()==1) return k==1;
    down(root);
    if(tree[lcd].cv>=k) return query(lcd,k);
    if(tree[lcd].rv+tree[rcd].lv>=k)
        return tree[lcd].r-tree[lcd].rv+1;
    if(tree[rcd].cv>=k) return query(rcd,k);
    return 0;
}

void update(int root,int l,int r,int col)
{
    if(tree[root].l==l && tree[root].r==r)
    {
        tree[root].col=col;
        tree[root].doit();
        return;
    }
    down(root);
    int m=tree[root].mid();
    if(r<=m) update(lcd,l,r,col);
    else if(l>m) update(rcd,l,r,col);
    else update(lcd,l,m,col),update(rcd,m+1,r,col);
    up(root);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,m,a,b,c;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        scanf("%d%d",&a,&b);
        if(a==1)
        {
            int s=query(1,b);
            printf("%d\n",s);
            if(s) update(1,s,s+b-1,1);
        }
        if(a==2) 
        {
            scanf("%d",&c);
            update(1,b,b+c-1,0);
        }
    }
}