1-n线段 m个操作
1 a
是否可找到连续a个空位子 有输出最左边（然后使这一段被占）没有0
2 a ,b
a~b区间变成未使用
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAXN 50010 struct node { int l,r,lsum,rsum,msum,la; }x[MAXN<<3]; void Build(int l,int r,int a) { x[a].l=l; x[a].r=r; x[a].lsum=x[a].rsum=x[a].msum=r-l+1; x[a].la=-1; if(l==r) return ; int mid=(l+r)>>1; Build(l,mid,a<<1); Build(mid+1,r,a<<1|1); } void push_down(int a) { int ll=x[a<<1].r-x[a<<1].l+1; int rr=x[a<<1|1].r-x[a<<1|1].l+1; x[a<<1].la=x[a<<1|1].la=x[a].la; x[a<<1].rsum=x[a<<1].lsum=x[a<<1].msum=x[a].la?0:ll; x[a<<1|1].rsum=x[a<<1|1].lsum=x[a<<1|1].msum=x[a].la?0:rr; x[a].la=-1; } void push_up(int a) { int ll=x[a<<1].r-x[a<<1].l+1; int rr=x[a<<1|1].r-x[a<<1|1].l+1; x[a].lsum=x[a<<1].lsum; if(x[a].lsum==ll)//区间合并 x[a].lsum+=x[a<<1|1].lsum; x[a].rsum=x[a<<1|1].rsum; if(x[a].rsum==rr) x[a].rsum+=x[a<<1].rsum; x[a].msum=max(max(x[a<<1].msum,x[a<<1|1].msum),x[a<<1].rsum+x[a<<1|1].lsum); } void update(int l,int r,int a1,int b1,int w,int a) { if(a1<=l&&r<=b1) { x[a].lsum=x[a].rsum=x[a].msum=w?0:(r-l+1); x[a].la=w; return ; } int mid=(l+r)>>1; if(x[a].la!=-1) push_down(a); if(a1<=mid) update(l,mid,a1,b1,w,a<<1); if(b1>mid) update(mid+1,r,a1,b1,w,a<<1|1); push_up(a); } int Ques(int l,int r,int w,int a) { if(l==r) return l; if(x[a].la!=-1) push_down(a); int mid=(l+r)>>1; if(x[a<<1].msum>=w)//左孩子最大连续区间够了 return Ques(l,mid,w,a<<1); else if(x[a<<1].rsum+x[a<<1|1].lsum>=w)//中间连续够了 return mid-x[a<<1].rsum+1; return Ques(mid+1,r,w,a<<1|1); //右边 } int main() { int n,m; scanf("%d%d",&n,&m); Build(1,n,1); while(m--) { int op,a,b; scanf("%d",&op); if(op==1) { scanf("%d",&a); if(x[1].msum<a)//最大的 printf("0 "); else { int p=Ques(1,n,a,1); printf("%d ",p); update(1,n,p,p+a-1,1,1);//变成使用 } } else { scanf("%d%d",&a,&b); update(1,n,a,a+b-1,0,1);//变成未使用 } } return 0; }