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 就是找一段長(zhǎng)為X的最左邊的區(qū)間，這個(gè)和HOTEL是沒有區(qū)別，還是用那三個(gè)函數(shù)找到最左邊的區(qū)間并加以更新，cov = 1
第二個(gè)指令是Free x就是找一個(gè)包含X的區(qū)間，咋一看以為要重寫一個(gè)QUERY函數(shù)，其實(shí)沒有必要，使用VECTOR數(shù)組保存下每次占領(lǐng)的區(qū)間，并且由于VECTOR是向量，可以刪除
中間的，并任意在中間加區(qū)間，十分方便。那我們現(xiàn)在向量里找到那個(gè)區(qū)間，接著進(jìn)行更新，cov = 0;
第三個(gè)指令是Get x就是找到第X個(gè)區(qū)間的范圍，用VECTOR的記錄很快就能找到
第四個(gè)指令Reset，很方面，更新一下即可
注意 二分不要寫錯(cuò)了 , 剛開始的 時(shí)候用的 lower_bound WA 到我想吐.................................
具體看代碼注釋
今天一早起來 繼續(xù)查錯(cuò)....... 一直很奇怪 為什么用 lower_bound 和 upper_bound 是 WA 的. 可能是早晨頭腦比較清醒, 半個(gè)小時(shí), 終于找到了錯(cuò)誤的原因 !
其實(shí)就是一個(gè)小小的錯(cuò)誤..... : 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標(biāo)記處理,返回
seg[rt].set ( flag ); return;
}
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( seg[rt].cov != -1 ) { // 如果線段不是混合情況(即線段是被覆蓋的), 把標(biāo)志下傳
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)); // 線段的更新, 經(jīng)典部分
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 ) { //線段為空,且可用,直接返回線段左端點(diǎn)
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 ); //因?yàn)榫€段已經(jīng)構(gòu)建好了, 更新下就可以了
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;
}