刚开始理解了poj的hotel，然后听说这题和hotel一样，本想着去刷题的，结果发现悲剧了，new操作确实一样，跟新也一样，但是free发现无从下手，最后看了别人的思路，想不到vector还有如此功能，今天算是学习了vector，挺神奇的。
#include<iostream> #include<cmath> #include<vector> using namespace std; #define maxn 50005 struct node { int left,right,lval,cval,rval,state; }; struct edge { int start,end; }; node st[maxn*4]; vector <edge> vv; int mymax(int a,int b,int c) { return max(max(a,b),c); } int len(int i) { return st[i].right-st[i].left+1; } void init(int i) { st[i].lval=st[i].rval=st[i].cval= st[i].state?0:len(i); } int bin_search(int x) { int left=0,right=vv.size()-1,mid; while(left<=right) { mid=(left+right)/2; if(vv[mid].start<=x) left=mid+1; if(vv[mid].start>x) right=mid-1; } return left; } void build(int l,int r,int i) { st[i].left=l,st[i].right=r; st[i].lval=st[i].rval=st[i].cval=r-l+1; st[i].state= i==1?0:-1; if(l==r) return ; int mid=(l+r)/2; build(l,mid,2*i); build(mid+1,r,2*i+1); return ; } int query(int i,int x) { if(st[i].left==st[i].right&&x==1) return st[i].left; if(st[i].state!=-1) { st[2*i].state=st[2*i+1].state=st[i].state; init(2*i); init(2*i+1); st[i].state=-1; } if(st[2*i].cval>=x) return query(2*i,x); else if(st[2*i].rval+st[2*i+1].lval>=x) return st[2*i].right-st[2*i].rval+1; else if(st[2*i+1].cval>=x) return query(2*i+1,x); else return 0; } void update(int l,int r,int i,int state) { if(st[i].left>=l&&st[i].right<=r) { st[i].state=state; init(i); return ; } if(st[i].state!=-1) { st[2*i].state=st[2*i+1].state=st[i].state; init(2*i); init(2*i+1); st[i].state=-1; } int mid=(st[i].left+st[i].right)/2; if(l<=mid) update(l,r,2*i,state); if(r>mid) update(l,r,2*i+1,state); st[i].lval=st[2*i].lval; st[i].rval=st[2*i+1].rval; st[i].cval=mymax(st[2*i].cval,st[2*i+1].cval, st[2*i].rval+st[2*i+1].lval); if(st[2*i].cval==len(2*i)) st[i].lval+=st[2*i+1].lval; if(st[2*i+1].cval==len(2*i+1)) st[i].rval+=st[2*i].rval; } int main() { char str[10]; int x,n,m,i,s,id; edge buf; while(scanf("%d%d",&n,&m)!=EOF) { vv.clear(); build(1,n,1); for(i=1;i<=m;i++) { scanf("%s",str); if(!strcmp(str,"Reset")) { st[1].state=0; init(1); vv.clear(); printf("Reset Now/n"); continue; } scanf("%d",&x); if(!strcmp(str,"New")) { s=query(1,x); if(!s) printf("Reject New/n"); else { printf("New at %d/n",s); update(s,s+x-1,1,1); id=bin_search(s); buf.start=s,buf.end=s+x-1; vv.insert(vv.begin()+id,buf); } } if(!strcmp(str,"Free")) { id=bin_search(x)-1; if(id<=-1) { printf("Reject Free/n"); continue; } else if(vv[id].end<x) printf("Reject Free/n"); else { printf("Free from %d to %d/n",vv[id].start ,vv[id].end); update(vv[id].start,vv[id].end,1,0); vv.erase(vv.begin()+id); } } if(!strcmp(str,"Get")) { if(vv.size()<x) printf("Reject Get/n"); else { x--; printf("Get at %d/n",vv[x].start); } } } printf("/n"); } return 0; }
