题意还是清楚的

就是维护很麻烦

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MAXN 50010struct node{    int l,r,la;    int ls,rs,ms;}x[MAXN<<3];struct no{    int l,r;};int n,m;vector
         
          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) //这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
           
            >1; if(z[mid].l<=a&&z[mid].r>=a) return mid; else if(z[mid].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
             
              ::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\n"); else { printf("New at %d\n",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\n"); else { // it = z.begin()+pos; printf("Free from %d to %d\n",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()