poj3667 hotel

#include <cstdio>
#define size 500010
#define Lson (x<<1),l,mid
#define Rson (x<<1|1),mid+1,r
int flag[size<<2],lc[size<<2],rc[size<<2],mc[size<<2];

int  max(int a,int b)
{
    return a>b?a:b;
}

void buildtree(int rt,int L,int R)
{
    flag[rt] = -1;
    lc[rt]=rc[rt]= mc[rt]= R-L+1;
    //printf("%d",mc[1]);
    if(L==R)
    {
        return ;
    }
    int mid = (L+R)/2;
    buildtree(rt*2,L,mid);
    buildtree(rt*2+1,mid+1,R);
}

void pushdown(int rt,int l,int r)
{
    if(flag[rt]!= -1)
    {
        int mid = (l+r)/2;
        flag[rt<<1]= flag[rt<<1|1]= flag[rt];
        mc[rt<<1]= lc[rt<<1]= rc[rt<<1] = flag[rt]?0:mid-l+1;
        mc[rt<<1|1]= lc[rt<<1|1] = rc[rt<<1|1]= flag[rt]?0:r-mid;
        flag[rt] = -1;
    }
}

int query(int a,int rt,int l,int r)
{
    if(l==r)
    {
        return l;
    }
    pushdown(rt,l,r);
    int mid = (l+r)/2;
    if(mc[rt<<1]>=a)
    {
        return query(a,rt*2,l,mid);
    }
    else if(lc[rt*2+1]+rc[rt*2]>= a)
    {
        return mid-rc[rt<<1]+1;
    }
    else
        return query(a,rt*2+1,mid+1,r);
}

void getup(int x,int l,int r)
{
    int mid=(l+r)/2;
    mc[x]=max(mc[x<<1],mc[x<<1|1]);
    mc[x]=max(mc[x],lc[x<<1|1]+rc[x<<1]);
    lc[x]=lc[x<<1]+ (lc[x<<1]==mid-l+1? lc[x<<1|1]:0);
    rc[x]=rc[x<<1|1]+(rc[x<<1|1]==r-mid? rc[x<<1]:0);
}

void color(int rt,int l,int r,int c,int L,int R)
{
    if(L<=l&&r<=R)
    {
        flag[rt] = c;
        mc[rt]= lc[rt]= rc[rt] = c?0:r-l+1;
        return ;
    }
    pushdown(rt,l,r);
    int mid = (l+r)/2;
    if(L<=mid)color(rt*2,l ,mid,c,L,R);
    if(R>mid)color(rt*2+1,mid+1,r,c,L,R);
    getup(rt,l,r);
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
       buildtree(1,1,n);
    while(m--)
    {
        int a,b,c;
        scanf("%d",&a);
        if(a==1)
        {
            scanf("%d",&b);
            if(mc[1]<b)puts("0");
            else{
                //puts("hahhahahha");
                int ans=query(b,1,1,n);
                printf("%d\n",ans);
                color(1,1,n,1,ans,ans+b-1);
            }
        }
        else
        {
            scanf("%d%d",&b,&c);
            color(1,1,n,0,b,b+c-1);
        }
    }
    }
    return 0;
}