HDU 2871 Memory Control (线段树+区间合并+成段更新+二分)

题意：给N个单位内存（编号从1开始），有4种操作。
（1）“Reset”，表示把所有的内存清空，然后输出"Reset Now"。
（2）“New x”，表示申请一块长度为x的内存块（如多解，左边优先），然后输出"New at A"，A表示该内存块的起点。
（3）“Free x”，表示把包含第x块单位内存的内存块清除，然后输出"Free from A to B"，A和B分别表示该内存块的起点和终点。
（4）“Get x”，表示返回第x块内存块的起始内存单位编号，然后输出 “Get at A”。

题解：线段树+区间合并+成段更新
我们用1表示空内存。

操作1就是成段更新。
操作2跟这题类似，就是普通的区间合并。

主要是操作3和4。
先来看3，要把包含第x个单位内存的内存块删除，所以我们要保存内存条上每一个点属于哪一个内存块，这里用懒惰标记$id$id表示，并用vector记录每一个$id$id的左右端点，然后通过queryPos()函数查询到叶子节点，返回属于哪一个内存块。

明白上面的，操作4就很简单了，我们用set维护每一个区间的左端点，因为vector插入不是按照顺序插入的，这样用set在删除的时候直接按值删除，插入即有序，然后暴力找第几个。

写完上面一段发现一种更好的方法，不需要用set，就是在插入的时候二分找到他应该在的位置，保证了有序，这样删除的时候也很方便了，操作4直接$O(1)$O(1)。不过代码还是按照原来的思路写的。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
const int MAXN = 5e4 + 5;
int sum[MAXN << 2], lsum[MAXN << 2], rsum[MAXN << 2], add[MAXN << 2], id[MAXN << 2];
struct Node {
    int l, r;
    int mid() { return (l + r) >> 1; }
} tree[MAXN << 2];

void PushDown(int rt, int m) {
    if (~add[rt]) {
        id[rt << 1] = id[rt];
        id[rt << 1 | 1] = id[rt];
        add[rt << 1] = add[rt];
        add[rt << 1 | 1] = add[rt];
        sum[rt << 1] = lsum[rt << 1] = rsum[rt << 1] = add[rt] * (m - (m >> 1));
        sum[rt << 1 | 1] = lsum[rt << 1 | 1] = rsum[rt << 1 | 1] = add[rt] * (m >> 1);
        add[rt] = -1;
    }
}
void PushUp(int rt) {
    int m = tree[rt].mid();
    sum[rt] = max(max(sum[rt << 1], sum[rt << 1 | 1]), rsum[rt << 1] + lsum[rt << 1 | 1]);
    lsum[rt] = lsum[rt << 1];
    rsum[rt] = rsum[rt << 1 | 1];
    if (lsum[rt] == (m - tree[rt].l + 1)) lsum[rt] += lsum[rt << 1 | 1];
    if (rsum[rt] == (tree[rt].r - m)) rsum[rt] += rsum[rt << 1];
}
void build(int l, int r, int rt) {
    tree[rt].l = l;
    tree[rt].r = r;
    add[rt] = -1;
    id[rt] = -1;
    if (l == r) {
        sum[rt] = lsum[rt] = rsum[rt] = 1;  //空房间置1
        return;
    }
    int m = tree[rt].mid();
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    PushUp(rt);
}
void update(int c, int l, int r, int rt, int ind) {
    if (tree[rt].l == l && r == tree[rt].r) {
        add[rt] = c;
        id[rt] = ind;
        sum[rt] = lsum[rt] = rsum[rt] = c * (r - l + 1);
        return;
    }
    if (tree[rt].l == tree[rt].r) return;
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    if (r <= m) update(c, l, r, rt << 1, ind);
    else if (l > m) update(c, l, r, rt << 1 | 1, ind);
    else {
        update(c, l, m, rt << 1, ind);
        update(c, m + 1, r, rt << 1 | 1, ind);
    }
    PushUp(rt);
}
int query(int c, int rt) {
    if (tree[rt].l == tree[rt].r) {
        return tree[rt].l;
    }
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    if (sum[rt] >= c) {
        if (sum[rt << 1] >= c) return query(c, rt << 1);
        else if (rsum[rt << 1] + lsum[rt << 1 | 1] >= c) return m - rsum[rt << 1] + 1;
        else return query(c, rt << 1 | 1);
    }
    return 0;
}
int queryPos(int x, int rt) {
    if (tree[rt].l == tree[rt].r) return id[rt];
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    if (x <= m) queryPos(x, rt << 1);
    else queryPos(x, rt << 1 | 1);
}
int n, m, x;
char s[11];
vector<int> st, ed;
set<int> se;
int main() {
    //freopen("in.txt", "r", stdin);
    while (~scanf("%d%d", &n, &m)) {
        st.clear();
        ed.clear();
        se.clear();
        build(1, n, 1);
        while (m--) {
            scanf("%s", s);
            if (s[0] == 'R') {
                st.clear();
                ed.clear();
                se.clear();
                update(1, 1, n, 1, -1);
                puts("Reset Now");
            }
            else if (s[0] == 'N') {
                scanf("%d", &x);
                int ans = query(x, 1);
                if (ans == 0) puts("Reject New");
                else {
                    printf("New at %d\n", ans);
                    st.push_back(ans);
                    ed.push_back(ans + x - 1);
                    se.insert(ans);
                    update(0, ans, ans + x - 1, 1, st.size() - 1);
                }
            }
            else if (s[0] == 'F') {
                scanf("%d", &x);
                int ind = queryPos(x, 1);
                if(ind == -1) puts("Reject Free");
                else {
                    printf("Free from %d to %d\n", st[ind], ed[ind]);
                    update(1, st[ind], ed[ind], 1, -1);
                    se.erase(st[ind]);
                }
            }
            else {
                scanf("%d", &x);
                if (x > se.size()) puts("Reject Get");
                else {
                    x--;
                    set<int>::iterator it = se.begin();
                    while (x--) it++;
                    printf("Get at %d\n", *it);
                }
            }
        }
        puts("");
    }
	return 0;
}