POJ3667 Hotel（Dec. 21th, 2018） 区间合并

// La Lune
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 50005
#define lhijo u << 1
#define rhijo u << 1 | 1
#define root 1, 1, n
#define lson lhijo, l, mid
#define rson rhijo, mid + 1, r
#define morb int u, int l, int r
using namespace std;
int t[N << 2], lu[N << 2], ne[N << 2], oc[N << 2], n, m;
// oc: 占领标记 occupation，-1表示未被操作，0表示被退房，1表示被占领 
// t, lu, ne 中的下标都是线段树中下标，lu表示左区间，ne表示右区间，要和以线段树中下标来区分的左儿子、右儿子区别开。 
void pushdown(int u, int m){
    if(oc[u] != -1){
        oc[lhijo] = oc[rhijo] = oc[u]; // 占领标记无差别传递 
        lu[lhijo] = ne[lhijo] = t[lhijo] = oc[u] ? 0 : (m - (m >> 1));
        lu[rhijo] = ne[rhijo] = t[rhijo] = oc[u] ? 0 : (m >> 1);
        // 若占领标记为1，则房间数为0，否则为区间长 
        oc[u] = -1;
    }
}
void build(morb){
    oc[u] = -1;
    t[u] = lu[u] = ne[u] = r - l + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    build(lson);
    build(rson);
}
void pushup(int u, int m){
    lu[u] = lu[lhijo];
    ne[u] = ne[rhijo];
    // 根的左区间取左儿子的左区间，右区间取右儿子的右区间 
    if(lu[u] == m - (m >> 1))
        lu[u] += lu[rhijo];
    // 若左儿子全空，则左儿子的总区间要与右儿子的左区间合并作为根的左区间 
    if(ne[u] == m >> 1)// 同理 
        ne[u] += ne[lhijo];
    t[u] = max(ne[lhijo] + lu[rhijo], max(t[lhijo], t[rhijo]));
    // 根的中区间从左儿子的中区间、右儿子的中区间、左儿子右区间与右儿子左区间的和中取最大值 
}
int query(morb, int w){ // query()返回的是初始房间序号 
    if(l == r) return 1;
    pushdown(u, r - l + 1);
    int mid = l + r >> 1;
    if(t[lhijo] >= w) // 如果左儿子中区间符合要求，就朝左搜 
        return query(lson, w);
    else if(ne[lhijo] + lu[rhijo] >= w) // 如果中间满足要求，直接返回下标: mid + 1 - 左儿子的右区间ne[lhijo] 
        return mid - ne[lhijo] + 1;
    else 
        return query(rson, w);
}
void update(morb, int a, int b, int c){
    if(a <= l && r <= b){
        t[u] = lu[u] = ne[u] = c ? 0 : r - l + 1;
        oc[u] = c;
        return;
    }
    pushdown(u, r - l + 1);
    int mid = l + r >> 1;
    if(a <= mid) update(lson, a, b, c);
    if(b > mid) update(rson, a, b, c);
    pushup(u, r - l + 1);
}
int main(){
    scanf("%d %d", &n, &m);
    build(root);
    while(m--){
        int ctrl, d;
        scanf("%d", &ctrl);
        if(ctrl == 1){
            scanf("%d", &d);
            if(t[1] < d){
                printf("0\n");
                continue;
            }
            int pos = query(root, d);
            update(root, pos, pos + d - 1, 1);
            printf("%d\n", pos);
        }
        else if(ctrl == 2){
            int l;
            scanf("%d %d", &l, &d);
            update(root, l, l + d - 1, 0);
        }
        else printf("Error.\n");
    }
    return 0;
}