poj 3667 Hotel(線段樹區間更新)

題目：​​http://poj.org/problem?id=3667​​

大意：有N個房間，給出M條語句，“1  a”表示要求查詢是否存在連續的a個空的房間，有的話輸出最左邊的一個，沒有的話輸出0。“2 a b"表示把從a開始的b個房間清空。

Sample Input

10 6

1 3

1 3

1 3

1 3

2 5 5

1 6

Sample Output

1

4

7

5

區間更新，區間查找。應用線段樹：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50005;  //query:詢問滿足條件的最左端點
struct Node
{
    int l,r;
    int lsum,rsum,msum; //三個值，幫助确定左邊，中間，右邊
    int tag;  //tag --> 标記，1是占用的，0是未占用，-1初始化
    int mid(){  return (l+r)/2; }
}tree[N<<2];

void pushdown(int root)//更新子樹tag,lsum,rsum,msum的資訊
{
    if(tree[root].tag != -1)
    {
        int l_num = tree[root*2].r - tree[root*2].l + 1;  //左子樹的長度
        int r_num = tree[root*2+1].r - tree[root*2+1].l + 1;  //右子樹的長度
        tree[root*2].tag = tree[root*2+1].tag = tree[root].tag;  //要處理
        tree[root].tag = -1;  //處理過了的
        tree[root*2].rsum = tree[root*2].lsum = tree[root*2].msum = tree[root*2].tag ?0:l_num;
        tree[root*2+1].rsum = tree[root*2+1].lsum = tree[root*2+1].msum = tree[root*2+1].tag ?0:r_num;
    }
}

void pushup(int root)//更新父節點lsum,rsum,msum的資訊,msum是最大的sum
{
    int l_num = tree[root*2].r - tree[root*2].l + 1;
    int r_num = tree[root*2+1].r - tree[root*2+1].l + 1;
    tree[root].lsum = tree[root*2].lsum;
    if(tree[root*2].lsum == l_num) tree[root].lsum += tree[root*2+1].lsum; //可向右拓展，越過中間

    tree[root].rsum = tree[root*2+1].rsum;
    if(tree[root].rsum == r_num) tree[root].rsum += tree[root*2].rsum; //可向左拓展，越過中間

    tree[root].msum = max(max(tree[root*2].msum,tree[root*2+1].msum),tree[root*2].rsum+tree[root*2+1].lsum);
}

void build(int l,int r,int root)
{
    tree[root].l = l,tree[root].r = r,tree[root].tag = -1;
    tree[root].lsum = tree[root].rsum = tree[root].msum = r-l+1;
    if(l == r) return;
    int m = (l+r)>>1;
    build(l,m,root*2);
    build(m+1,r,root*2+1);
    pushup(root);
}

void update(int l,int r,int tg,int root)
{
    if(tree[root].l == l && tree[root].r == r)
    {
        tree[root].msum = tree[root].lsum = tree[root].rsum = tg?0:(r-l+1);
        tree[root].tag = tg;
        return;
    }
    pushdown(root);  //更新子樹資訊
    int m = tree[root].mid();
    if(r<=m) update(l,r,tg,root*2);
    else if(l>m) update(l,r,tg,root*2+1);
    else
    {
        update(l,m,tg,root*2);
        update(m+1,r,tg,root*2+1);
    }
    pushup(root);  //回溯資訊。
}

int query(int w,int root)
{
    if (tree[root].l == tree[root].r) return tree[root].l;
    pushdown(root); //依據tag更新資訊再統計
    int m = tree[root].mid();
    if (tree[root*2].msum >= w) return query(w,root*2);  //這段代碼很重要
    else if (tree[root*2].rsum + tree[root*2+1].lsum >= w)//中間的情況
        return m - tree[root*2].rsum + 1;  //主要依靠中間區域和葉子節點傳回資訊
    return query(w,root*2+1);  //右邊
}

int main()
{
    //freopen("cin.txt","r",stdin);
    int n,m;
    while(cin>>n>>m)
    {
        build(1,n,1);
        while(m--)
        {
            int p;
            scanf("%d",&p);
            if(p == 1)
            {
                int a;
                scanf("%d",&a);
                if(tree[1].msum < a) puts("0");
                else
                {
                    int ans = query(a,1);
                    printf("%d\n",ans);
                    update(ans,ans+a-1,1,1);
                }
            }
            else
            {
                int a,b;
                scanf("%d %d",&a,&b);
                update(a,a+b-1,0,1);
            }
        }
    }
    return 0;
}