POJ 3667 Hotel（區間合並）

題意：賓館有n個房間。有人來入住。共有2種操作

思路：裸的區間合並。每個結點區間[l，r]存從左端點l開始向右最大連續空房間數lm，從右端點r開始向左最大連續空房間數rm和當前區間內最大連續空房間數。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

const int N = 5e5 + 10;
const int INF = 0x7f7f7f7f;

struct Node {
    int lm;
    int rm;
    int mx;

    Node() {}

    Node(int x, int y, int z) {
        lm = x;
        rm = y;
        mx = z;
    }
};

Node node[N << 2];
int lazy[N << 2];

void pushup(int rt, int l, int r) {
    int m = (l + r) >> 1;
    node[rt].mx = max(node[rt << 1].rm + node[rt << 1 | 1].lm, 
                    max(node[rt << 1].mx, node[rt << 1 | 1].mx));
    if (node[rt << 1].lm == m - l + 1)
        node[rt].lm = node[rt << 1].lm + node[rt << 1 | 1].lm;
    else 
        node[rt].lm = node[rt << 1].lm;
    if (node[rt << 1 | 1].rm == r - m)
        node[rt].rm = node[rt << 1 | 1].rm + node[rt << 1].rm;
    else 
        node[rt].rm = node[rt << 1 | 1].rm;
}

void pushdown(int rt, int l, int r) {
    if (lazy[rt] != -1) {
        lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
        int m = (l + r) >> 1;
        int lenl = m - l + 1;
        int lenr = r - m;
        if (lazy[rt] == 1) {
            node[rt << 1] = Node(lenl, lenl, lenl);
            node[rt << 1 | 1] = Node(lenr, lenr, lenr);
        }
        else {
            node[rt << 1] = Node(0, 0, 0);
            node[rt << 1 | 1] = Node(0, 0, 0);
        }
        lazy[rt] = -1;
    }
}

void build(int l, int r, int rt) {
    lazy[rt] = -1;
    node[rt].lm = node[rt].rm = node[rt].mx = r - l + 1;
    if (l == r)
        return ;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
}

void update(int t, int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
        if (t == 1)
            node[rt] = Node(r - l + 1, r - l + 1, r - l + 1);
        else
            node[rt] = Node(0, 0, 0);
        lazy[rt] = t;
        return ;
    }
    if (l == r)
        return ;
    pushdown(rt, l, r);
    int m = (l + r) >> 1;
    if (L <= m)
        update(t, L, R, lson);
    if (R > m)
        update(t, L, R, rson);
    pushup(rt, l, r);
}

int query(int t, int l, int r, int rt) {
    if (l == r)
        return l;
    int m = (l + r) >> 1;
    pushdown(rt, l, r);
    int p;
    if (node[rt << 1].mx >= t)
        p = query(t, lson);
    else if (node[rt << 1].rm + node[rt << 1 | 1].lm >= t)
        p = m - node[rt << 1].rm + 1;
    else 
        p = query(t, rson);
    pushup(rt, l, r);
    return p;
}


int main() {

    int n, m;
    while (scanf(%d%d, &n, &m) != EOF) {
        build(1, n, 1);
        for (int i_q = 1; i_q <= m; i_q++) {
            int q;
            scanf(%d, &q);
            if (q == 1) {
                int d;
                scanf(%d, &d);
                if (node[1].mx < d) {//不需要更新。wa了n發
                    puts(0);
                    continue;
                }
                int l = query(d, 1, n, 1);
                printf(%d
, l);
                update(0, l, l + d - 1, 1, n, 1);
            }
            else {
                int x, d;
                scanf(%d%d, &x, &d);
                update(1, x, x + d - 1, 1, n, 1);
            }
        }
    }
    return 0;
}