HDU2871内存管理问题（线段树优化）

#include 
#include 
#include 
using namespace std;

#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define root 1, n, 1
#define ls l, m, rt <<1
#define rs m + 1, r, rt <<1 | 1
#define Max(a, b) ((a) > (b) ? (a) : (b))

struct edge {
    int l, r;
    bool operator<(const edge& b) const { return l };

const int maxn = 50010;
int n, m, num, ll[maxn <<2], rr[maxn <<2], lazy[maxn <<2], mlen[maxn <<2];
vector Q;

inline void pup(int l, int r, int rt) {
    int m = (l + r) >> 1;
    mlen[rt] = Max(mlen[rt <<1], mlen[rt <<1 | 1]);
    mlen[rt] = Max(mlen[rt], rr[rt <<1] + ll[rt <<1 | 1]);
    ll[rt] = ll[rt <<1] + (ll[rt <<1] == m - l + 1 ? ll[rt <<1 | 1] : 0);
    rr[rt] = rr[rt <<1 | 1] + (rr[rt <<1 | 1] == r - m ? rr[rt <<1] : 0);
}

inline void pdown(int l, int r, int rt) {
    if (lazy[rt] != -1) {
        lazy[rt <<1] = lazy[rt <<1 | 1] = lazy[rt];
        int m = (l + r) >> 1;
        mlen[rt <<1] = ll[rt <<1] = rr[rt <<1] = (lazy[rt] == 0 ? m - l + 1 : 0);
        mlen[rt <<1 | 1] = rr[rt <<1 | 1] = ll[rt <<1 | 1] = (lazy[rt] == 0 ? r - m : 0);
        lazy[rt] = -1;
    }
}

int New(int l, int r, int rt, int num) {
    if (l == r) return l;
    int m = (l + r) >> 1;
    pdown(l, r, rt);
    if (mlen[rt <<1] >= num) return New(ls, num);
    else if (rr[rt <<1] + ll[rt <<1 | 1] >= num) return m - rr[rt <<1] + 1;
    else return New(rs, num);
}

void covr(int op, int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
        lazy[rt] = op;
        ll[rt] = rr[rt] = mlen[rt] = (op == 0 ? r - l + 1 : 0);
        return;
    }
    pdown(l, r, rt);
    int m = (l + r) >> 1;
    if (L <= m) covr(op, L, R, ls);
    if (R > m) covr(op, L, R, rs);
    pup(l, r, rt);
}

void reset() {
    Q.clear();
    Q.push_back(edge{0, 0});
    Q.push_back(edge{100000, 100000});
    covr(0, 1, n, root);
}

void insert(edge xx) {
    int now = upper_bound(Q.begin(), Q.end(), xx) - Q.begin();
    Q.insert(Q.begin() + now, xx);
}

int main() {
    char op[20];
    edge s = {0, 0}, e = {100000, 100000};
    while (~scanf("%d%d", &n, &m)) {
        reset();
        while (m--) {
            scanf("%s", op);
            if (op[0] != 'R') scanf("%d", &num);
            if (op[0] == 'N') {
                if (mlen[1]                 else {
                    int x = New(root, num);
                    printf("New at %d\n", x);
                    edge tp = {x, x + num - 1};
                    covr(1, tp.l, tp.r, root);
                    insert(tp);
                }
            } else if (op[0] == 'F') {
                edge tp = {num, num};
                int now = upper_bound(Q.begin(), Q.end(), tp) - Q.begin() - 1;
                if (Q[now].l <= num && Q[now].r >= num) {
                    covr(0, Q[now].l, Q[now].r, root);
                    printf("Free from %d to %d\n", Q[now].l, Q[now].r);
                    Q.erase(Q.begin() + now);
                } else puts("Reject Free");
            } else if (op[0] == 'G') {
                if (num > Q.size() - 2) puts("Reject Get");
                else printf("Get at %d\n", Q[num].l);
            } else {
                reset();
                puts("Reset Now");
            }
        }
        puts("");
    }
    return 0;
}