#include <cstdio>

// poj 1823

enum {ARRIVE = 1, LEAVE = 2, REPORT = 3};
struct node_t {
    int max_empty, left_empty, right_empty;
};

const int N = 16001;
node_t tr[N * 16];

#define LSON(k) (k * 2)
#define RSON(k) (k * 2 + 1)
#define MAX(x, y) (x > y ? x : y)

void build(int nd, int l, int r)
{
    tr[nd].max_empty = tr[nd].left_empty =
    tr[nd].right_empty = r - l + 1;
    if (l == r)
        return;
    int m = (l + r) / 2;
    build(LSON(nd), l, m);
    build(RSON(nd), m + 1, r);
}

void collect(int nd, int l, int r)
{
    int lson = LSON(nd);
    int rson = RSON(nd);
    int m = (l + r) / 2;
    int union_max_empty = tr[lson].right_empty +
                          tr[rson].left_empty;
    tr[nd].max_empty = MAX(union_max_empty,
                           MAX(tr[lson].max_empty,
                               tr[rson].max_empty));
    tr[nd].left_empty = tr[lson].left_empty;
    tr[nd].right_empty = tr[rson].right_empty;

    if (tr[lson].left_empty == m - l + 1)
        tr[nd].left_empty += tr[rson].left_empty;
    if (tr[rson].right_empty == r - m)
        tr[nd].right_empty += tr[lson].right_empty;
}

void insert(int nd, int l, int r, int lo, int ro)
{
    if (lo <= l && ro >= r) {
        tr[nd].max_empty = tr[nd].left_empty =
        tr[nd].right_empty = 0;
        return;
    }
    if (l == r)
        return;
    int m = (l + r) / 2;
    if (lo <= m) 
        insert(LSON(nd), l, m, lo, ro);
    if (ro > m)
        insert(RSON(nd), m + 1, r, lo, ro);

    collect(nd, l, r);
}

void remove(int nd, int l, int r, int lo, int ro)
{
    if (lo <= l && ro >= r) {
        tr[nd].max_empty = tr[nd].left_empty = 
        tr[nd].right_empty = r - l + 1;
        return;
    }
    if (l == r)
        return;
    if (tr[nd].max_empty == 0) {
        tr[LSON(nd)].max_empty = tr[LSON(nd)].left_empty =
        tr[LSON(nd)].right_empty = 0;
        tr[RSON(nd)].max_empty = tr[RSON(nd)].left_empty =
        tr[RSON(nd)].right_empty = 0;
    }
    int m = (r + l) / 2;
    if (lo <= m)
        remove(LSON(nd), l, m, lo, ro);
    if (ro > m)
        remove(RSON(nd), m + 1, r, lo, ro);

    collect(nd, l, r);
}

int main()
{
    int n, p;
    scanf("%d%d", &n, &p);
    build(1, 1, n);
    for (int i = 1; i <= p; ++i) {
        int type, x, y;
        scanf("%d", &type);
        switch (type) {
            case ARRIVE:
                scanf("%d%d", &x, &y);
                insert(1, 1, n, x, x + y - 1);
                break;
            case LEAVE:
                scanf("%d%d", &x, &y);
                remove(1, 1, n, x, x + y - 1);
                break;
            case REPORT:
                printf("%d\n", tr[1].max_empty);
                break;
        }
    }
}

• Re:能给点测试数据吗？俺一直wa (5) loganecolss 2013-01-27 16:11:42