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を1回行う.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
", 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
", 
                                                       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
", G[num - 1].s);

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

                printf("
");
        }

        return 0;
}