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的最左邊的區(qū)間，這個和HOTEL是沒有區(qū)別，還是用那三個函數找到最左邊的區(qū)間并加以更新，cov = 1
第二個指令是Free x就是找一個包含X的區(qū)間，咋一看以為要重寫一個QUERY函數，其實沒有必要，使用VECTOR數組保存下每次占領的區(qū)間，并且由于VECTOR是向量，可以刪除
中間的，并任意在中間加區(qū)間，十分方便。那我們現(xiàn)在向量里找到那個區(qū)間，接著進行更新，cov = 0;
第三個指令是Get x就是找到第X個區(qū)間的范圍，用VECTOR的記錄很快就能找到
第四個指令Reset，很方面，更新一下即可
注意 二分不要寫錯了 , 剛開始的 時候用的 lower_bound WA 到我想吐.................................
具體看代碼注釋
今天一早起來 繼續(xù)查錯....... 一直很奇怪 為什么用 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://m.shnenglu.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 沒區(qū)別
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;
}