用线段树维护区间中最大的一段连续的1，以左端点为左端点最大的一段连续的1，以右端点为右端点最大的一段连续的1，然后就可以支持区间修改和查询了
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 50005 4 #define L (k<<1) 5 #define R (L+1) 6 #define mid (l+r>>1) 7 int n,m,p,x,y,f[N<<3],ls[N<<3],rs[N<<3],laz[N<<3]; 8 void up(int k,int l,int r){ 9 if (laz[k]>=0)f[k]=ls[k]=rs[k]=laz[k]*(r-l+1); 10 else{ 11 f[k]=max(max(f[L],f[R]),rs[L]+ls[R]); 12 ls[k]=ls[L]+(ls[L]==(mid-l+1))*ls[R]; 13 rs[k]=rs[R]+(rs[R]==(r-mid))*rs[L]; 14 } 15 } 16 void down(int k,int l,int r){ 17 if (laz[k]<0)return; 18 laz[L]=laz[R]=laz[k]; 19 f[L]=ls[L]=rs[L]=laz[L]*(mid-l+1); 20 f[R]=ls[R]=rs[R]=laz[R]*(r-mid); 21 laz[k]=-1; 22 } 23 void update(int k,int l,int r,int x,int y,int p){ 24 if ((l>y)||(x>r))return; 25 if ((x<=l)&&(r<=y)){ 26 f[k]=ls[k]=rs[k]=p*(r-l+1); 27 laz[k]=p; 28 return; 29 } 30 down(k,l,r); 31 update(L,l,mid,x,y,p); 32 update(R,mid+1,r,x,y,p); 33 up(k,l,r); 34 } 35 int query(int k,int l,int r,int x){ 36 down(k,l,r); 37 if (f[L]>=x)return query(L,l,mid,x); 38 if (rs[L]+ls[R]>=x)return mid-rs[L]+1; 39 return query(R,mid+1,r,x); 40 } 41 int main(){ 42 scanf("%d%d",&n,&m); 43 memset(laz,-1,sizeof(laz)); 44 update(1,1,n,1,n,1); 45 for(int i=1;i<=m;i++){ 46 scanf("%d",&p); 47 if (p==1){ 48 scanf("%d",&x); 49 if (f[1]<x)y=0; 50 else y=query(1,1,n,x); 51 printf("%d ",y); 52 if (y)update(1,1,n,y,y+x-1,0); 53 } 54 else{ 55 scanf("%d%d",&x,&y); 56 update(1,1,n,x,x+y-1,1); 57 } 58 } 59 }