题意还是清楚的
就是维护很麻烦
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> using namespace std; #define MAXN 50010 struct node { int l,r,la; int ls,rs,ms; }x[MAXN<<3]; struct no { int l,r; }; int n,m; vector<no>z; void Build(int l,int r,int a) { x[a].l=l; x[a].r=r; x[a].la=-1; x[a].ls=x[a].rs=x[a].ms=r-l+1; if(l == r) return ; int mid=(l+r)>>1; Build(l,mid,a<<1); Build(mid+1,r,a<<1|1); } char s1[10]; void push_down(int a)//下更 { x[a<<1].la=x[a<<1|1].la=x[a].la; int r,l,mid; l=x[a].l; r=x[a].r; mid=(r+l)>>1; if(x[a].la==1) { x[a<<1].ls=x[a<<1].rs=x[a<<1].ms=mid-l+1; x[a<<1|1].ls=x[a<<1|1].rs=x[a<<1|1].ms=r-mid; } else { x[a<<1].ls=x[a<<1].rs=x[a<<1].ms=0; x[a<<1|1].ls=x[a<<1|1].rs=x[a<<1|1].ms=0; } x[a].la=-1; } void push_up(int a)//上更 { x[a].ls=x[a<<1].ls; if(x[a].ls==x[a<<1].r-x[a<<1].l+1) x[a].ls+=x[a<<1|1].ls; x[a].rs=x[a<<1|1].rs; if(x[a].rs==x[a<<1|1].r-x[a<<1|1].l+1) x[a].rs+=x[a<<1].rs; x[a].ms=max(x[a<<1].ms,x[a<<1|1].ms); x[a].ms=max(x[a].ms,x[a<<1].rs+x[a<<1|1].ls); } int Ques(int a,int len) { if(x[a].la!=-1) push_down(a); int mid=(x[a].r+x[a].l)>>1; if(x[a].ms<len) return 0; else { if(x[a].ls>=len) //这4个很重要 return x[a].l; else if(x[a<<1].ms>=len) return Ques(a<<1,len); else if(x[a<<1].rs+x[a<<1|1].ls>=len) return mid-x[a<<1].rs+1; else return Ques(a<<1|1,len); } push_up(a); } int b_search(int a) { int l=0,r=z.size()-1; while(l<=r) { int mid=(l+r)>>1; if(a<z[mid].l) r=mid-1; else l=mid+1; } return l; } int b_search1(int a) { int l=0,r=z.size()-1; while(l<=r) { int mid=(l+r)>>1; if(z[mid].l<=a&&z[mid].r>=a) return mid; else if(z[mid].r<a) l=mid+1; else r=mid-1; } return -1; } void Update(int l,int r,int a1,int b1,int a) //变成都被占用 { if(a1<=l&&r<=b1) { x[a].la=0; x[a].ls=x[a].rs=x[a].ms=0; return ; } if(x[a].la!=-1) push_down(a); int mid=(l+r)>>1; if(a1<=mid) Update(l,mid,a1,b1,a<<1); if(b1>mid) Update(mid+1,r,a1,b1,a<<1|1); push_up(a); } void Update1(int l,int r,int a1,int b1,int a)//变成都不被占用 { if(a1<=l&&r<=b1) { x[a].la=1; x[a].ls=x[a].rs=x[a].ms=r-l+1; return ; } if(x[a].la!=-1) push_down(a); int mid=(l+r)>>1; if(a1<=mid) Update1(l,mid,a1,b1,a<<1); if(b1>mid) Update1(mid+1,r,a1,b1,a<<1|1); push_up(a); } int main() { while(scanf("%d%d",&n,&m) != EOF) { Build(1,n,1); z.clear(); vector<no>::iterator it; no p1; while(m--) { scanf("%s",s1); if(strcmp(s1,"New") == 0) //查询这段区间存不存在 { int a; scanf("%d",&a); int pos=Ques(1,a); if(pos == 0) printf("Reject New "); else { printf("New at %d ",pos); Update(1,n,pos,pos+a-1,1); //更新 it=z.begin()+b_search(pos); p1.l=pos; p1.r=pos+a-1; z.insert(it,p1); } } else if(strcmp(s1,"Free") == 0)//二分 这个点有没有被使用 { int a; scanf("%d",&a); int pos=b_search1(a); if(pos == -1) printf("Reject Free "); else { // it = z.begin()+pos; printf("Free from %d to %d ",it->l,it->r); Update1(1,n,it->l,it->r,1); z.erase(it); } } else if(strcmp(s1,"Get") == 0) { int a; scanf("%d",&a); if(z.size()<a) printf("Reject Get "); else printf("Get at %d ",z[a-1].l); } else //全部都释放的话lazy一下 { x[1].la=1; x[1].ls=x[1].rs=x[1].ms=n; printf("Reset Now "); z.clear(); } } printf(" "); } return 0; }