用vector进行插入和删除操作！
总是有些地方处理不好，对拍了才知道错在哪里，，
/* 给定一些操作 reset 清空 new a ，申请最左边的连续a个空间 free a，清空a所在的块 get x，求第x块的起始地址 用个vector<pair<int,int> >记录第i个块的覆盖区间 new时二分找到a所在的pair，进行insert 清空时二分找到a所在的pair，进行erase即可 求第x块的起始地址只要去vector里找一下即可 */ #include<bits/stdc++.h> #include<vector> using namespace std; #define maxn 50005 int n,m; vector<pair<int,int> >v; vector<pair<int,int> >::iterator it; int cmp(pair<int,int> a,pair<int,int> b){return a.first<b.first;} #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int lazy[maxn<<2],mx[maxn<<2],lmx[maxn<<2],rmx[maxn<<2]; void set0(int l,int r,int rt){mx[rt]=lmx[rt]=rmx[rt]=lazy[rt]=0;} void set1(int l,int r,int rt){mx[rt]=lmx[rt]=rmx[rt]=r-l+1;lazy[rt]=1;} void pushup(int l,int r,int rt){ lmx[rt]=lmx[rt<<1],rmx[rt]=rmx[rt<<1|1]; mx[rt]=max(mx[rt<<1],mx[rt<<1|1]); mx[rt]=max(mx[rt],rmx[rt<<1]+lmx[rt<<1|1]); int m=l+r>>1; if(lmx[rt<<1]==m-l+1)lmx[rt]=lmx[rt<<1|1]+m-l+1; if(rmx[rt<<1|1]==r-m)rmx[rt]=rmx[rt<<1]+r-m; } void pushdown(int l,int r,int rt){ int m=l+r>>1; if(lazy[rt]==-1)return; else if(lazy[rt]==0)set0(lson),set0(rson); else set1(lson),set1(rson); lazy[rt]=-1; } void build(int l,int r,int rt){ lazy[rt]=-1; if(l==r){mx[rt]=lmx[rt]=rmx[rt]=1;return;} int m=l+r>>1; build(lson);build(rson); pushup(l,r,rt); } void update0(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){set0(l,r,rt);return;} int m=l+r>>1; pushdown(l,r,rt); if(L<=m)update0(L,R,lson); if(R>m)update0(L,R,rson); pushup(l,r,rt); } void update1(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){set1(l,r,rt);return;} int m=l+r>>1; pushdown(l,r,rt); if(L<=m)update1(L,R,lson); if(R>m)update1(L,R,rson); pushup(l,r,rt); } int query(int cnt,int l,int r,int rt){ if(l==r)return l; pushdown(l,r,rt); int m=l+r>>1; if(cnt<=mx[rt<<1])return query(cnt,lson); else if(cnt<=rmx[rt<<1]+lmx[rt<<1|1])return m-rmx[rt<<1]+1; else return query(cnt,rson); } int main(){ while(cin>>n>>m){ build(1,n,1); v.clear(); while(m--){ char opt[10];int a; scanf("%s",opt); if(opt[0]!='R')scanf("%d",&a); if(opt[0]=='N'){//申请连续a个空间 if(mx[1]<a){ puts("Reject New"); continue; } int pos=query(a,1,n,1); printf("New at %d\n",pos); update0(pos,pos+a-1,1,n,1);//这一段被占用了 pair<int,int>tmp=make_pair(pos,pos+a-1); it=upper_bound(v.begin(),v.end(),tmp,cmp); v.insert(it,tmp); } if(opt[0]=='F'){//释放a所在的块 pair<int,int>tmp=make_pair(a,a); it=upper_bound(v.begin(),v.end(),tmp,cmp);//找第一个比tmp大的块 int p=it-v.begin()-1; if(p==-1 || v[p].second<a){ puts("Reject Free"); continue; } printf("Free from %d to %d\n",v[p].first,v[p].second); update1(v[p].first,v[p].second,1,n,1); v.erase(v.begin()+p); } if(opt[0]=='R'){ update1(1,n,1,n,1); v.clear(); puts("Reset Now"); } if(opt[0]=='G'){ if(v.size()<a)puts("Reject Get"); else printf("Get at %d\n",v[a-1].first); } } puts(""); } }
转载于:https://www.cnblogs.com/zsben991126/p/10631827.html
