POJ 3667 Hotel

題目大意：   1 a:詢問是不是有連續長度為a的空房間,有的話住進最左邊   2 a b:將[a,a+b-1]的房間清空   思路：線段樹的區間合並。   用cov記錄區段的狀態，-1代表沒有被更新，0代表空閒，1代表是有人入住的。   用lmax代表從左端點開始最長的空閒區間，rmax代表從右開始最長的區間。tree代表自己這個區間內擁有的最大區間。   接下來就是兩個重要的函數：pushdown  pushup了   void pushup(int num,int mid) {     lmax[num]=lmax[num<<1];     rmax[num]=rmax[num<<1|1];     if(lmax[num]==(mid-(mid>>1)))lmax[num]+=lmax[num<<1|1];     if(rmax[num]==(mid>>1))rmax[num]+=rmax[num<<1];     tree[num]=max(tree[num<<1],max(tree[num<<1|1],rmax[num<<1]+lmax[num<<1|1])); }     首先在不考慮左右最大區間重疊的情況下，左邊最大區間是左兒子的最大左區間，右邊的最大區間是又兒子的最大右區間。   當lmax[num]==(mid-(mid>>1))時，就代表左邊全部是空閒的，就要考慮一個最大的區間被分成了兩邊了，就再加上右兒子的最大左區間。   同理。   最後更新最大區間的時候  就要三者做比較    最大的左  最大的右   左右之間的部分。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 50005
using namespace std;

int tree[MAXN<<2];
int lmax[MAXN<<2];
int rmax[MAXN<<2];
int cov[MAXN<<2];

void pushup(int num,int mid)
{
    lmax[num]=lmax[num<<1];
    rmax[num]=rmax[num<<1|1];
    if(lmax[num]==(mid-(mid>>1)))lmax[num]+=lmax[num<<1|1];
    if(rmax[num]==(mid>>1))rmax[num]+=rmax[num<<1];
    tree[num]=max(tree[num<<1],max(tree[num<<1|1],rmax[num<<1]+lmax[num<<1|1]));
}

void pushdown(int num,int mid)
{
    if(cov[num]!=-1)
    {
        cov[num<<1] = cov[num<<1|1] = cov[num];
        tree[num<<1] = lmax[num<<1] = rmax[num<<1] = cov[num] ? 0: (mid - (mid>>1));
        tree[num<<1|1] = lmax[num<<1|1] = rmax[num<<1|1] = cov[num] ? 0:(mid>>1);
        cov[num]=-1;
    }
}


void build(int num,int l,int r)
{
    lmax[num] = rmax[num] = tree[num] = r - l + 1;
    cov[num] = -1;
    if(r==l)return;
    int mid = (r+l)>>1;
    build(num<<1,l,mid);
    build(num<<1|1,mid+1,r);
}


int query(int num,int s,int e,int w)
{
    if(e==s)
    return s;
    pushdown(num,e-s+1);
    int mid = (s+e)>>1;

    if(tree[num<<1]>=w)return query(num<<1,s,mid,w);
    else if(rmax[num<<1] + lmax[num<<1|1] >=w)return mid + 1 - rmax[num<<1];

    return query(num<<1|1,mid+1,e,w);
}

void update(int num,int s,int e,int l,int r,int v)
{
    if(l<=s && e<=r)
    {
        tree[num] = lmax[num] = rmax[num] = v ? 0 : e-s+1;
        cov[num] = v;
        return ;
    }
    pushdown(num,e-s+1);
    int mid = (e+s)>>1;
    if(l<=mid)update(num<<1,s,mid,l,r,v);
    if(r>mid)update(num<<1|1,mid+1,e,l,r,v);
    pushup(num,e-s+1);
}


int main()
{
    int n,m;

        scanf("%d%d",&n,&m);
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d",&a);

            if(a==1)
            {
                scanf("%d",&b);
                if(tree[1]<b)puts("0");
                else {
                int p=query(1,1,n,b);
                printf("%d\n",p);
                update(1,1,n,p,p+b-1,1);
                }
            }
            else
            {
                scanf("%d%d",&b,&c);
                update(1,1,n,b,b+c-1,0);
            }
        }
        return 0;
}