POJ 3667 Hotel 線段樹區間合并

這道題應該算是比較經典的線段樹了

題意是：

這座巨型飯店在一條超長走廊上有N（1 ≤ N ≤ 50000）個排成一排的房間，每個房間都能欣賞到蘇必利爾湖的好景色。現在所有的房間都是空的。

現在Bessie等旅客們正在不斷地發出訂房和退房要求。你需要接受M（1 ≤ M < 50000）條指令：

每條指令的第一個數字為1或2。如果是1，後面将有一個整數D表示顧客要預定的房間數。注意，這些房間必須是連續的。如果能夠滿足旅客的訂房要求， 輸出滿足要求的第一個房間的編号（例如，要訂房6間，輸出3表示3, 4, 5, 6, 7, 8是滿足要求的），這樣的編号必須是可能的編号裡面最靠前的。如果不能滿足要求，輸出0。

如果是2，後面将有兩個整數X和D表示顧客要退掉X, X + 1, X + 2, ... , X + D - 1這D間房。對于這樣的指令什麼都不輸出

線段樹儲存的資訊有，cover代表是否有人，msum代表區間内最大的連續長度，lsum是從左結點往右的連續長度，rsum是從右結點往左的連續長度。

/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 50005
#define INF 10000000000000000LL
#define L(x) x<<1
#define R(x) x<<1|1
#define PI acos(-1.0)
#define eps 1e-7
using namespace std;
struct node
{
    int left, right, mid;
    int cover, lsum, rsum, msum;
}tree[4 * MAXN];
void down(int C)
{
    if(tree[C].cover != -1)
    {
        int p = tree[C].right - tree[C].left + 1;
        tree[L(C)].cover = tree[R(C)].cover = tree[C].cover;
        tree[L(C)].lsum = tree[L(C)].rsum = tree[L(C)].msum = tree[C].cover ? 0 : p - (p >> 1);
        tree[R(C)].lsum = tree[R(C)].rsum = tree[R(C)].msum = tree[C].cover ? 0 : (p >> 1);
        tree[C].cover = -1;
    }
}
void up(int C)
{
    int p = tree[C].right - tree[C].left + 1;
    tree[C].lsum = tree[L(C)].lsum;
    tree[C].rsum = tree[R(C)].rsum;
    if(tree[C].lsum == p - (p >> 1)) tree[C].lsum += tree[R(C)].lsum;
    if(tree[C].rsum == (p >> 1)) tree[C].rsum += tree[L(C)].rsum;
    tree[C].msum = max(tree[R(C)].lsum + tree[L(C)].rsum, max(tree[L(C)].msum, tree[R(C)].msum));
}
void make_tree(int s, int e, int C)
{
    tree[C].left = s;
    tree[C].right = e;
    tree[C].mid = (s + e) >> 1;
    tree[C].cover = -1;
    tree[C].lsum = tree[C].rsum = tree[C].msum = e - s + 1;
    if(s == e) return;
    make_tree(s, tree[C].mid, L(C));
    make_tree(tree[C].mid + 1, e, R(C));
}
void update(int s, int e, int p, int C)
{
    if(tree[C].left >= s && tree[C].right <= e)
    {
        tree[C].msum = tree[C].lsum = tree[C].rsum = p ? 0: tree[C].right - tree[C].left + 1;
        tree[C].cover = p;
        return;
    }
    down(C);
    if(tree[C].mid >= s) update(s, e, p, L(C));
    if(tree[C].mid < e) update(s, e, p, R(C));
    up(C);
}
int query(int p, int C)
{
    if(tree[C].left == tree[C].right) return tree[C].left;
    down(C);
    if(tree[L(C)].msum >= p) return query(p, L(C));
    else if(tree[L(C)].rsum + tree[R(C)].lsum >= p) return tree[C].mid - tree[L(C)].rsum + 1;
    else return query(p, R(C));
}
int main()
{
    int n, m, op, x, y;
    scanf("%d%d", &n, &m);
    make_tree(1, n, 1);
    while(m--)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d", &x);
            if(tree[1].msum < x) puts("0");
            else
            {
                int p = query(x, 1);
                printf("%d\n", p);
                update(p, p + x - 1, 1, 1);
            }
        }
        else
        {
            scanf("%d%d", &x, &y);
            update(x, x + y - 1, 0, 1);
        }
    }
    return 0;
}