HDOJ 2871 Memory Control（线段树区间合并与查询）

思路：

hotel的加强版。把申请到的内存都放到vector容器里面，然后再利用STL里面的upper_bound函数操作即可。写完之后感觉很爽。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define lhs l, m, rt << 1
#define rhs m + 1, r, rt << 1 | 1

const int maxn = 50010;
int sum[maxn << 2], lsum[maxn << 2], rsum[maxn << 2];
int lab[maxn << 2];

enum __op { __free = 0, __new };

typedef struct _node {
    int beg, end;
    _node(int _b, int _e) : beg(_b), end(_e) { };
    friend bool operator < (const _node& n1, const _node& n2) { return n1.beg < n2.beg; };
} node ;

void PushUp(int l, int r, int rt)
{
    lsum[rt] = lsum[rt << 1];
    rsum[rt] = rsum[rt << 1 | 1];

    int m = (l + r) >> 1;
    if (lsum[rt] == m - l + 1)
        lsum[rt] += lsum[rt << 1 | 1];
    if (rsum[rt] == r - m)
        rsum[rt] += rsum[rt << 1];

    sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
    sum[rt] = max(rsum[rt << 1] + lsum[rt << 1 | 1], sum[rt]);
}

void PushDown(int l, int r, int rt)
{
    if (lab[rt] != -1)
    {
        int m = (l + r) >> 1;
        lab[rt << 1] = lab[rt << 1 | 1] = lab[rt];
        sum[rt << 1] = lsum[rt << 1] = rsum[rt << 1] = lab[rt] ? 0 : m - l + 1;
        sum[rt << 1 | 1] = lsum[rt << 1 | 1] = rsum[rt << 1 | 1] = lab[rt] ? 0 : r - m;
        lab[rt] = -1;
    }
}

int Query(int size, int l, int r, int rt)
{
    if (l == r)
        return r;

    int m = (l + r) >> 1;
    PushDown(l, r, rt);

    if (sum[rt << 1] >= size)
        return Query(size, lhs);
    else if (rsum[rt << 1] + lsum[rt << 1 | 1] >= size)
        return m - rsum[rt << 1] + 1;
    else 
        return Query(size, rhs);

    // PushUp(l, r, rt);
}

void Update(int beg, int end, __op op, int l, int r, int rt)
{
    if (beg <= l && r <= end)
    {
        sum[rt] = lsum[rt] = rsum[rt] = op ? 0 : r - l + 1;
        lab[rt] = op;
        return ;
    }
    PushDown(l, r, rt);

    int m = (l + r) >> 1;
    if (beg <= m)
        Update(beg, end, op, lhs);
    if (end > m)
        Update(beg, end, op, rhs);

    PushUp(l, r, rt);
}

void Build(int l, int r, int rt)
{
    sum[rt] = r - l + 1;
    lsum[rt] = rsum[rt] = r - l + 1;
    lab[rt] = -1;

    if (l == r)
        return ;

    int m = (l + r) >> 1;
    Build(lhs), Build(rhs);
}

int main()
{
    int n, m;
    vector<node> mblk;

    while (~scanf("%d %d", &n, &m))
    {
        Build(1, n, 1);

        mblk.clear();
        for (int i = 0; i < m; ++i)
        {
            char op[16]; 
            scanf("%s", op);

            if (op[0] == 'N')
            {
                int x;
                scanf("%d", &x);
                if (sum[1] >= x)
                {
                    int p = Query(x, 1, n, 1);
                    vector<node>::iterator iter;

                    Update(p, p + x - 1, __new, 1, n, 1);
                    printf("New at %d\n", p);

                    iter = upper_bound(mblk.begin(), mblk.end(), node(p, p + x - 1));
                    mblk.insert(iter, node(p, p + x - 1));
                }
                else
                    printf("Reject New\n");
            }
            else if (op[0] == 'F')
            {
                int x;
                scanf("%d", &x);
                int p = upper_bound(mblk.begin(), mblk.end(), node(x, x)) - mblk.begin() - 1;

                if (p == -1 || mblk[p].end < x)
                    printf("Reject Free\n");
                else
                {
                    printf("Free from %d to %d\n", mblk[p].beg, mblk[p].end);
                    Update(mblk[p].beg, mblk[p].end, __free, 1, n, 1);
                    mblk.erase(mblk.begin() + p);
                }
            }
            else if (op[0] == 'G')
            {
                int x;
                scanf("%d", &x);
                if (x <= mblk.size())
                    printf("Get at %d\n", mblk[x-1].beg);
                else
                    printf("Reject Get\n");
            }
            else if (op[0] == 'R')
            {
                Update(1, n, __free, 1, n, 1);
                // Build(1, n, 1);
                mblk.clear();
                printf("Reset Now\n");
            }
        }
        printf("\n");
    }
    return 0;
}