一共4种操作
其中用线段树 区间合并，来维护连续空的长度，和找出那个位置。其他用vector维护即可
#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include <iostream> #include<vector> #define lson i<<1 #define rson i<<1|1 #define N 50050 using namespace std; struct node { int l,r; }; bool operator<(node a,node b) { return a.l<b.l; } vector<node>e; int lsum[N*4],rsum[N*4],msum[N*4]; int flag[N*4]; inline int max(int x,int y) { return x>y?x:y; } void pushup(int i,int l,int r) { int mid=(l+r)>>1; lsum[i]=lsum[lson]; rsum[i]=rsum[rson]; if(lsum[i]==mid-l+1) lsum[i]+=lsum[rson]; if(rsum[i]==r-mid) rsum[i]+=rsum[lson]; msum[i]=max(msum[lson],msum[rson]); msum[i]=max(msum[i],rsum[lson]+lsum[rson]); } void pushdown(int i,int l,int r) { if(flag[i]!=-1) { int mid=(l+r)>>1; flag[lson]=flag[rson]=flag[i]; lsum[lson]=rsum[lson]=msum[lson]=(mid-l+1)*flag[i]; lsum[rson]=rsum[rson]=msum[rson]=(r-mid)*flag[i]; flag[i]=-1; } } void build(int l,int r,int i) { flag[i]=-1; lsum[i]=rsum[i]=msum[i]=r-l+1; if(l==r) return ; int mid=(l+r)>>1; build(l,mid,lson); build(mid+1,r,rson); } void update(int l,int r,int pl,int pr,int va,int i) { if(l>=pl&&r<=pr) { flag[i]=va; rsum[i]=lsum[i]=msum[i]=(r-l+1)*va; return ; } pushdown(i,l,r); int mid=(l+r)>>1; if(pl<=mid)update(l,mid,pl,pr,va,lson); if(pr>mid)update(mid+1,r,pl,pr,va,rson); pushup(i,l,r); } int query(int l,int r,int va,int i) { if(msum[i]==r-l+1) return l; pushdown(i,l,r); int mid=(l+r)>>1; if(msum[lson]>=va) return query(l,mid,va,lson); else if(rsum[lson]+lsum[rson]>=va) return mid-rsum[lson]+1; else return query(mid+1,r,va,rson); } int main() { int n,m; char s[20]; while(scanf("%d%d",&n,&m)!=EOF) { build(1,n,1); e.clear(); while(m--) { int x; vector<node>::iterator it; node d; scanf(" %s",s); if(s[0]=='N') { scanf("%d",&x); if(msum[1]<x) puts("Reject New"); else { int tmp=query(1,n,x,1); printf("New at %d ",tmp); d.l=tmp;d.r=tmp+x-1; update(1,n,tmp,tmp+x-1,0,1); it=upper_bound(e.begin(),e.end(),d); e.insert(it,d); } } else if(s[0]=='F') { scanf("%d",&x); d.l=x;d.r=x; it=upper_bound(e.begin(),e.end(),d); int tmp=it-e.begin()-1; if(tmp<0||e[tmp].l>x||e[tmp].r<x) printf("Reject Free "); else { printf("Free from %d to %d ",e[tmp].l,e[tmp].r); update(1,n,e[tmp].l,e[tmp].r,1,1); e.erase(e.begin()+tmp); } } else if(s[0]=='G') { scanf("%d",&x); if(e.size()<x) puts("Reject Get"); else printf("Get at %d ",e[x-1].l); } else { update(1,n,1,n,1,1); e.clear(); puts("Reset Now"); } } printf(" "); } return 0; }