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 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.
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.
第一哥指令 New x 就是找一段长为X的最左边的区间，这个和HOTEL是没有区别，还是用那三个函数找到最左边的区间并加以更新，cov = 1
第二个指令是Free x就是找一个包含X的区间，咋一看以为要重写一个QUERY函数，其实没有必要，使用VECTOR数组保存下每次占领的区间，并且由于VECTOR是向量，可以删除
中间的，并任意在中间加区间，十分方便。那我们现在向量里找到那个区间，接着进行更新，cov = 0;
第三个指令是Get x就是找到第X个区间的范围，用VECTOR的记录很快就能找到
第四个指令Reset，很方面，更新一下即可
注意 二分不要写错了 , 刚开始的 时候用的 lower_bound WA 到我想吐.................................
具体看代码注释
今天一早起来 继续查错....... 一直很奇怪 为什么用 lower_bound 和 upper_bound 是 WA 的. 可能是早晨头脑比较清醒, 半个小时, 终于找到了错误的原因 !
其实就是一个小小的错误..... : modify ( it->beg, it->end, 0 );
vec.erase ( it );
我写成了 这样 : vec.erase ( it );
modify ( it->beg, it->end, 0 );
竟然把迭代器删除了再 使用 .... 
杯具.........................
代码如下 :
/*
Mail to : miyubai@gamil.com
Link : http://www.cnblogs.com/MiYu || http://www.cppblog.com/MiYu
Author By : MiYu
Test : 2
Complier : g++ mingw32-3.4.2
Program : HDU_2871
Doc Name : Memory Control
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
inline int max ( int a, int b ) {
return a > b ? a : b;
}
struct segTree {
int left, right, lVal, rVal, mVal, cov;// cov -- > 0: 线段为空 1: 线段为满 -1：2种情况都有
int mid () { return (left+right)>>1; }
int dis () { return right - left + 1; }
void set ( int flag ) { // 0: 线段为空 1: 线段为满
if ( flag ){
cov = 1;
lVal = rVal = mVal = 0;
} else {
cov = 0;
lVal = rVal = mVal = right - left + 1;
}
}
}seg[150010];
void creat ( int left, int right, int rt = 1 ) { // 初始化线段
seg[rt].left = left;
seg[rt].right = right;
seg[rt].set (0);
if ( left == right ) return;
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
creat ( left, mid, LL );
creat ( mid + 1, right, RR );
}
void modify ( int left, int right, int flag, int rt = 1 ) {
if ( seg[rt].left >= left && seg[rt].right <= right ) { //如果线段被覆盖, 直接按flag标记处理,返回
seg[rt].set ( flag ); return;
}
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( seg[rt].cov != -1 ) { // 如果线段不是混合情况(即线段是被覆盖的), 把标志下传
seg[LL].cov = seg[RR].cov = seg[rt].cov;
seg[LL].set ( seg[LL].cov );
seg[RR].set ( seg[RR].cov );
}
if ( right <= mid ) modify ( left, right, flag, LL ); //递归更新线段
else if ( left > mid ) modify ( left, right, flag, RR );
else {
modify ( left, mid, flag, LL );
modify ( mid + 1, right, flag, RR );
}
if ( seg[LL].cov == 0 && seg[RR].cov == 0 ) seg[rt].cov = 0; //线段为空
else if ( seg[LL].cov == 1 && seg[RR].cov == 1 ) seg[rt].cov = 1; //线段满
else seg[rt].cov = -1; // 2种情况都有
seg[rt].mVal = max(seg[LL].rVal+seg[RR].lVal,max(seg[LL].mVal, seg[RR].mVal)); // 线段的更新, 经典部分
seg[rt].lVal = seg[LL].lVal + ( seg[LL].cov == 0 ? seg[RR].lVal : 0 );
seg[rt].rVal = seg[RR].rVal + ( seg[RR].cov == 0 ? seg[LL].rVal : 0 );
}
int query ( int val, int rt = 1 ) {
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( seg[rt].cov == 0 && seg[rt].mVal >= val ) { //线段为空,且可用,直接返回线段左端点
return seg[rt].left;
} else if ( seg[rt].cov == -1 ) { //分三种 情况处理 左 左右 右 处理
if ( seg[LL].mVal >= val ) return query ( val, LL );
else if ( seg[LL].rVal + seg[RR].lVal >= val ) return mid - seg[LL].rVal + 1;
else if ( seg[RR].mVal >= val )return query ( val, RR );
}
return 0;
}
struct P {
int beg, end;
void set(int &a, int b) { beg = a; end = b; }
friend bool operator < ( const P& a, const P& b ) {
return a.beg < b.beg;
}
};
vector <P> vec;
vector <P>::iterator it;
int find ( int &x ) { // 2分找满足要求的线段的下一条线段
int beg = 0;
int end = vec.size() - 1;
while ( beg <= end ) {
int mid = ( beg + end ) >> 1;
if ( vec[mid].beg <= x ) {
beg = mid + 1;
} else {
end = mid - 1;
}
}
return beg;
}
inline bool scan_ud(int &num)
{
char in;
in=getchar();
if(in==EOF) return false;
while(in<'0'||in>'9') in=getchar();
num=in-'0';
while(in=getchar(),in>='0'&&in<='9'){
num*=10,num+=in-'0';
}
return true;
}
int main ()
{
int N, M, left, right, val, choice;
char ask[10];
P temp, tt;
while ( scan_ud(N)&& scan_ud(M) ) {
creat ( 1, N );
vec.clear();
while ( M -- ) {
scanf ( "%s",ask );
switch ( ask[0] ) {
case 'R' : modify ( 1, N, 0 ); //因为线段已经构建好了, 更新下就可以了
vec.clear(); //记得 vec clear() 一下
puts ( "Reset Now" );
break;
case 'N' : scan_ud( val );
left = query ( val ); // 和 PKU3667 没区别
if ( left == 0 || seg[1].mVal < val ) puts ( "Reject New" );
else {
modify ( left, left + val - 1 , 1 );
temp.set( left,left+val-1 );
right = find ( left );
vec.insert ( vec.begin() + right, temp );
printf ( "New at %d\n",left );
}
break;
case 'F' : scan_ud( val );
right = find ( val ) - 1;
if ( right == -1 || vec[right].end < val ) { //没找到
puts("Reject Free");
} else {
printf ( "Free from %d to %d\n", vec[right].beg, vec[right].end );
modify ( vec[right].beg, vec[right].end, 0 );
vec.erase ( vec.begin() + right );
}
break;
case 'G' : scan_ud( val );
if ( val > vec.size() ) // 直接输出就行
puts ( "Reject Get" );
else {
printf ( "Get at %d\n",vec[val-1].beg );
}
}
}
putchar ( 10 );
}
return 0;
}