Memory Control（线段树 + vector + 区间合并）

Memory Control

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4429    Accepted Submission(s): 1060

Problem Description

Memory units are numbered from 1 up to N.
A sequence of memory units is called a memory block.
The memory control system we consider now has four kinds of operations:
1.  Reset Reset all memory units free.
2.  New x Allocate a memory block consisted of x continuous free memory units with the least start number
3.  Free x Release the memory block which includes unit x
4.  Get x Return the start number of the xth memory block(Note that we count the memory blocks allocated from left to right)
Where 1<=x<=N.You are request to find out the output for M operations.

 

 

Input

Input contains multiple cases.
Each test case starts with two integer N,M(1<=N,M<=50000) ,indicating that there are N units of memory and M operations.
Follow by M lines,each line contains one operation as describe above.

 

 

Output

For each “Reset” operation, output “Reset Now”.
For each “New” operation, if it’s possible to allocate a memory block,
output “New at A”,where Ais the least start number,otherwise output “Reject New”.
For each “Free” operation, if it’s possible to find a memory block occupy unit x,
output “Free from A to B”,where A and B refer to the start and end number of the memory block,otherwise output “Reject Free”.
For each “Get” operation, if it’s possible to find the xth memory blocks,
output “Get at A”,where A is its start number,otherwise output “Reject Get”.
Output one blank line after each test case.

 

 

Sample Input

6 10

New 2

New 5

New 2

New 2

Free 3

Get 1

Get 2

Get 3

Free 3

Reset

 

 

Sample Output

New at 1

Reject New

New at 3

New at 5

Free from 3 to 4

Get at 1

Get at 5

Reject Get

Reject Free

Reset Now

 

       题意：

       给出 N（1 ~ 50000）， M（1 ~ 50000），代表有 N 个记忆块，M 个操作。有 4 类操作，New 说明要申请连续 ans 个的记忆块，Free 说明要解除包含 ans 这个数的记忆块，Get 说明要输出第 ans 个的记忆块的起始编号，Reject 说明要初始化所有的记忆。

 

       思路：

       线段树 + vector + 区间统计。New 操作就是区间合并操作，每次 New 完按起点由小到大顺序插入到 vector 中，Free 和 Get 操作都可以用 upper_bound 操作取得，Reject 则是 vector 的 clear 操作，因为是多组数据，所以每次开始前都要 clear 一次。否则会导致 TLE。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 50005 * 10;

typedef struct {
        int s, e;
} node;

vector<node> G;
int memory[MAX];
int lmax[MAX], rmax[MAX], mmax[MAX];

bool cmp (node a, node b) {
        return a.s < b.s;
}

void push_down(int node, int l, int r) {
        if (memory[node] != -1) {
                memory[node << 1] = memory[node];
                memory[node << 1 | 1] = memory[node];

                int mid = (r + l) >> 1;
                mmax[node << 1] = lmax[node << 1] =
                rmax[node << 1] = (memory[node] ? 0 : mid - l + 1);

                mmax[node << 1 | 1] = lmax[node << 1 | 1] =
                rmax[node << 1 | 1] = (memory[node] ? 0 : r - mid);

                memory[node] = -1;
        }
}

void push_up(int node, int l, int r) {
        int mid = (r + l) >> 1;

        lmax[node] = lmax[node << 1];
        rmax[node] = rmax[node << 1 | 1];
        if (lmax[node] == mid - l + 1)
            lmax[node] += lmax[node << 1 | 1];
        if (rmax[node] == r - mid)
            rmax[node] += rmax[node << 1];

        mmax[node] = max( rmax[node << 1] + lmax[node << 1 | 1],
                          max(mmax[node << 1], mmax[node << 1 | 1]) );

}

void build (int node, int l, int r) {
        if (l == r) {
                mmax[node] = lmax[node] = rmax[node] = 1;
                memory[node] = -1;

        } else {
                int mid = (r + l) >> 1;
                build(node << 1, l, mid);
                build(node << 1 | 1, mid + 1, r);

                memory[node] = -1;
                push_up(node, l, r);
        }
}

void updata (int node, int l, int r, int al, int ar, int s) {
        if (al > r || ar < l) return;
        if (al <= l && ar >= r) {
                memory[node] = s;
                mmax[node] = lmax[node] = rmax[node] =
                                (s ? 0 : r - l + 1);
                return;
        }

        push_down(node, l, r);
        int mid = (r + l) >> 1;
        if (al <= mid) updata(node << 1, l, mid, al, ar, s);
        if (ar > mid) updata(node << 1 | 1, mid + 1, r, al, ar, s);
        push_up(node, l, r);
}

int query (int node, int l, int r, int num) {
        if (l == r) return l;

        push_down(node, l, r);
        int mid = (r + l) >> 1;
        if (mmax[node << 1] >= num)
            return query(node << 1, l, mid, num);
        else if (rmax[node << 1] + lmax[node << 1 | 1] >= num)
            return (mid - rmax[node << 1] + 1);
        return query(node << 1 | 1, mid + 1, r, num);
}

int main() {
        int n, m;

        while (~scanf("%d%d", &n, &m)) {
                build (1, 1, n);
                G.clear();

                while (m--) {
                        char op[10];
                        int num;
                        scanf("%s", op);

                        if (!strcmp(op, "New")) {

                                scanf("%d", &num);
                                if (mmax[1] < num) puts("Reject New");
                                else {
                                        node in;
                                        in.s = query(1, 1, n, num);
                                        in.e = in.s + num - 1;

                                        vector<node>::iterator it;
                                        it = 
                                            upper_bound(G.begin(), G.end(), in, cmp);
                                        G.insert(it, in);

                                        printf("New at %d\n", in.s);
                                        updata(1, 1, n, in.s, in.e, 1);
                                }

                        } else if (!strcmp(op, "Free")) {
                                node in;
                                scanf("%d", &in.s);
                                in.e = in.s;

                                vector<node>::iterator it;
                                it = upper_bound(G.begin(), G.end(), in, cmp);
                                if (it == G.begin()) puts("Reject Free");
                                else {
                                        --it;
                                        if ((it -> e) < in.s) puts("Reject Free");
                                        else {
                                                printf("Free from %d to %d\n", 
                                                       it -> s, it -> e);
                                                updata(1, 1, n, it -> s, 
                                                       it -> e, 0);
                                                G.erase(it);
                                        }
                                }

                        } else if (!strcmp(op, "Get")) {
                                scanf("%d", &num);
                                if (num > G.size()) puts("Reject Get");
                                else printf("Get at %d\n", G[num - 1].s);

                        } else if (!strcmp(op, "Reset")) {
                                updata(1, 1, n, 1, n, 0);
                                puts("Reset Now");
                                G.clear();
                        }
                }

                printf("\n");
        }

        return 0;
}