Memory Control(线段树+区间合并)

Memory Control

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

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 10New 2New 5New 2New 2Free 3Get 1Get 2Get 3Free 3Reset

 

Sample Output

New at 1Reject NewNew at 3New at 5 Free from 3 to 4Get at 1Get at 5Reject GetReject Free

Reset Now

#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 50010 << 2
#define max(x,y) (x)>(y)?x:y
using namespace std;
struct {
	int llen;
	int rlen;
	int mlen;
}tree[maxn];
struct unit {
	int l, r;
	unit() {}
	unit(int l, int r) :l(l), r(r) {}
	bool operator <(unit& b) const {
		return this->l < b.l;
	}
};
vector<unit> v;
int lazy[maxn];
int N, M;
int T;
int X;
char op[10];


// 更新节点值
void PushUp(int l, int r, int p) {
	// left_len
	if (tree[p << 1].llen == ((r + l) >> 1) - l + 1)
		tree[p].llen = tree[p << 1].llen + tree[p << 1 | 1].llen;
	else
		tree[p].llen = tree[p << 1].llen;
	// right_len
	if (tree[p << 1 | 1].rlen == r - ((r + l) >> 1))
		tree[p].rlen = tree[p << 1 | 1].rlen + tree[p << 1].rlen;
	else
		tree[p].rlen = tree[p << 1 | 1].rlen;
	// maxlen
	tree[p].mlen = max(tree[p << 1].rlen + tree[p << 1 | 1].llen, max(tree[p << 1].mlen, tree[p << 1 | 1].mlen));
}

void PushDown(int l, int r, int p) {
	int m = (l + r) >> 1;
	if (lazy[p] != 0) {
		lazy[p << 1] = lazy[p << 1 | 1] = lazy[p];
		tree[p << 1].llen = tree[p << 1].rlen = tree[p << 1].mlen = lazy[p] == -1 ? (m - l) + 1 : 0;
		tree[p << 1 | 1].llen = tree[p << 1 | 1].rlen = tree[p << 1 | 1].mlen = lazy[p] == -1 ? r - m : 0;
		lazy[p] = 0;
	}
}

// 构造函数
void Build(int l, int r, int p) {
	lazy[p] = 0;
	if (l == r) {
		tree[p].llen = tree[p].rlen = tree[p].mlen = 1;
		return;
	}
	int m = (l + r) >> 1;
	Build(l, m, p << 1);
	Build(m + 1, r, p << 1 | 1);
	PushUp(l, r, p);
}

// 区域操作
void Update(int L, int R, int C, int l, int r, int p) {
	if (L <= l && r <= R) {
		if (C == -1) {
			tree[p].llen = tree[p].rlen = tree[p].mlen = r - l + 1;
			lazy[p] = -1;
		}
		else {
			tree[p].llen = tree[p].rlen = tree[p].mlen = 0;
			lazy[p] = 1;
		}
		return;
	}
	int m = (l + r) >> 1;
	PushDown(l, r, p);
	if (L <= m)
		Update(L, R, C, l, m, p << 1);
	if (R >= m + 1)
		Update(L, R, C, m + 1, r, p << 1 | 1);
	PushUp(l, r, p);
}

// 查询操作
int Query(int C, int l, int r, int p) {
	if (l == r)
		return l;
	int m = (l + r) >> 1;
	PushDown(l, r, p);
	if (tree[p << 1].mlen >= C)
		return Query(C, l, m, p << 1);
	else if (tree[p << 1].rlen + tree[p << 1 | 1].llen >= C)
		return m - tree[p << 1].rlen + 1;
	else if (tree[p << 1 | 1].mlen >= C)
		return Query(C, m + 1, r, p << 1 | 1);
}

int find(int X) {
	int l = 0;
	int r = v.size() - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (v[mid].l <= X && X <= v[mid].r)
			return mid;
		else if (v[mid].l > X)
			r = mid - 1;
		else if (v[mid].r < X)
			l = mid + 1;
	}
	return -1;
}


int main() {
	//freopen("1.txt", "r", stdin);
	while (scanf("%d %d", &N, &M) == 2) {
		Build(1, N, 1);
		v.clear();
		while (M--) {
			scanf("%s", op);
			if (op[0] == 'N') {
				scanf("%d", &X);
				if (tree[1].mlen < X)
					printf("Reject New\n");
				else {
					int pos = Query(X, 1, N, 1);
					Update(pos, pos + X - 1, 1, 1, N, 1);
					printf("New at %d\n", pos);
					v.insert(upper_bound(v.begin(), v.end(), unit(pos, pos + X - 1)), unit(pos, pos + X - 1));
				}
			}
			else if (op[0] == 'F') {
				scanf("%d", &X);
				int pos = find(X);
				if (pos == -1)
					printf("Reject Free\n");
				else {
					printf("Free from %d to %d\n", v[pos].l, v[pos].r);
					Update(v[pos].l, v[pos].r, -1, 1, N, 1);
					v.erase(v.begin() + pos);
				}
			}
			else if (op[0] == 'G') {
				scanf("%d", &X);
				if (v.size() < X)
					printf("Reject Get\n");
				else
					printf("Get at %d\n", v[X - 1].l);
			}
			else if (op[0] == 'R') {
				Update(1, N, -1, 1, N, 1);
				v.clear();
				printf("Reset Now\n");
			}
		}
		printf("\n");
	}
	return 0;
}