這題有點(diǎn)像Hotel的包裝版，非常經(jīng)典，讓我進(jìn)一步熟悉了線段樹(shù)的區(qū)間操作（主要是延遲標(biāo)記的使用）。
唯一的問(wèn)題出在自己寫(xiě)的二分函數(shù)上，死活都是TLE，后來(lái)參考了小HH的二分才過(guò)掉，不知道自己哪寫(xiě)掛了，郁悶。。。。
PS:順便問(wèn)一下，高質(zhì)量的內(nèi)存管理難道真的是用線段樹(shù)實(shí)現(xiàn)的？
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int const maxn=50010;
int n,m;
#define LL(i) (i<<1)
#define RR(i) ((i<<1)|1)
struct node
{
int l,r;
int cval,lval,rval;
int st;
int len(){return r-l+1;}
void doit()
{
if(st==1)cval=lval=rval=0;
else cval=lval=rval=len();
}
}ST[maxn*8];
struct block
{
int s,t;
};
vector<block>B;
/**//*
int Bfind(int x)//返回-1代表沒(méi)找到
{
int l=0;
int r=B.size()-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(x>=B[mid].s&&x<=B[mid].t)return mid;
if(x<B[mid].s)r=mid-1;
else if(x>B[mid].t)l=mid+1;
}
return -1;
}
int Infind(int x)//找到插入位置
{
int l=0;
int r=B.size()-1;
int len=B.size();
while(l<=r)
{
if(x>B[len-1].t)
return B.size();
if(x<B[0].s)
return 0;
int mid=(l+r)>>1;
if(x>B[mid].t&&x<B[mid+1].s)return mid+1;
if(x<B[mid].s) r=mid-1;
else if(x>B[mid].t)l=mid+1;
}
}
*/
int Bin(int x) {
int lo = 0;
int hi =B.size()- 1;
while(lo <= hi) {
int mid = (lo + hi) >> 1;
if(B[mid].s<= x) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return lo;
}
//st為0時(shí)代表沒(méi)覆蓋
void Build(int l,int r,int i)
{
ST[i].st=0;
ST[i].l=l;
ST[i].r=r;
if(l==r){ST[i].cval=ST[i].lval=ST[i].rval=1;return;}
int mid=(ST[i].l+ST[i].r)>>1;
Build(l,mid,LL(i));
Build(mid+1,r,RR(i));
ST[i].cval=ST[i].lval=ST[i].rval=ST[i].len();
}
void update(int l,int r,int op,int i)
{
if(l==ST[i].l&&r==ST[i].r)
{
ST[i].st=op;
ST[i].doit();
return;
}
if(ST[i].st!=-1)
{
ST[LL(i)].st=ST[RR(i)].st=ST[i].st;
ST[LL(i)].doit();
ST[RR(i)].doit();
ST[i].st=-1;
}
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)update(l,r,op,LL(i));
else if(l>mid)update(l,r,op,RR(i));
else{
update(l,mid,op,LL(i));
update(mid+1,r,op,RR(i));
}
ST[i].cval=max(ST[LL(i)].cval,ST[RR(i)].cval);
ST[i].cval=max(ST[i].cval,ST[LL(i)].rval+ST[RR(i)].lval);
//
ST[i].lval=ST[LL(i)].lval;
ST[i].rval=ST[RR(i)].rval;
//
if(ST[LL(i)].lval==ST[LL(i)].len())
ST[i].lval+=ST[RR(i)].lval;
if(ST[RR(i)].rval==ST[RR(i)].len())
ST[i].rval+=ST[LL(i)].rval;
}
int Query(int w,int i)
{
if(ST[i].lval>=w)return ST[i].l;
if(ST[i].st!=-1)
{
ST[LL(i)].st=ST[RR(i)].st=ST[i].st;
ST[LL(i)].doit();
ST[RR(i)].doit();
ST[i].st=-1;
}
else if(ST[LL(i)].cval>=w)return Query(w,LL(i));
else if(ST[LL(i)].rval+ST[RR(i)].lval>=w) return ST[LL(i)].r-ST[LL(i)].rval+1;
else if(ST[RR(i)].cval>=w)return Query(w,RR(i));
//else if(ST[RR(i)].rval>=w)return ST[RR(i)].r-ST[RR(i)].rval+1;
else return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
Build(1,n,1);
B.clear();
for(int i=0;i<m;i++)
{
char op[9];
scanf("%s",op);
if(op[0]=='N')
{
int w;
scanf("%d",&w);
if(ST[1].cval<w)
puts("Reject New");
else
{
//
int s=Query(w,1);
update(s,s+w-1,1,1);
printf("New at %d\n",s);
//
block tem;
tem.s=s;
tem.t=s+w-1;
int pos=Bin(s);
B.insert(B.begin()+pos,tem);
}
}
else if(op[0]=='R')
{
update(1,n,0,1);
puts("Reset Now");
B.clear();
}
else if(op[0]=='G')
{
int x;
scanf("%d",&x);
if(x>B.size())
puts("Reject Get");
else
{
printf("Get at %d\n",B[x-1].s);
}
}
else
{
int x;
scanf("%d",&x);
int t=Bin(x)-1;
if(t==-1||B[t].t<x)
puts("Reject Free");
else
{
printf("Free from %d to %d\n",B[t].s,B[t].t);
update(B[t].s,B[t].t,0,1);
B.erase(B.begin()+t,B.begin()+t+1);
}
}
}
puts("");
}
return 0;
}