简单的线段树维护区间信息。
维护三个值，一个是从左端点能拓展的长度，一个是从右端点能脱产的的长度。另一个是整个区间内的最大连续零一长度。
记录这三个值的目的在于可以使小区间合并大区间。
这样话就可以愉快的跑出答案了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using std::max;
using std::min;
const int maxn=50100;
struct node
{
int lmax;//从左端点开始拓展的最长长度
int rmax;//右端点开始
int Max;//区间内的最大长度
int tag;//懒标记
void fill(int a=0,int b=0,int c=0,int d=0)//默认参数
{
if(b&&!c&&!d) d=c=b;//用于减少代码量
tag=a;lmax=b;rmax=c;Max=d;
return ;
}
};
node T[maxn<<2];
void push_up(int l,int r,int mid,int R)
{
T[R].lmax=T[R<<1].lmax;//左右区间直接赋值
T[R].rmax=T[R<<1|1].rmax;
if(T[R<<1].lmax==mid-l+1) T[R].lmax+=T[R<<1|1].lmax;//如果左端点直接跨越了整个左区间
if(T[R<<1|1].rmax==r-mid) T[R].rmax+=T[R<<1].rmax;//同上
T[R].Max=max(max(T[R<<1].Max,T[R<<1|1].Max),T[R<<1].rmax+T[R<<1|1].lmax);//取最大，切记要加上后面这一大坨
return ;
}
void push_down(int l,int r,int mid,int R)
{
if(!T[R].tag) return ;
if(T[R].tag==1)
{
T[R<<1].fill(1);
T[R<<1|1].fill(1);//整段区间归零
}
else
{
T[R<<1].fill(2,mid-l+1);
T[R<<1|1].fill(2,r-mid);//整段区间重置
}
T[R].tag=0;
return;
}
void build(int l,int r,int R)
{
if(l==r)
{
T[R].fill(0,1);//赋初值
return ;
}
int mid=(l+r)>>1;
build(l,mid,R<<1);
build(mid+1,r,R<<1|1);
push_up(l,r,mid,R);//合并
}
void updata(int l,int r,int al,int ar,int R,int mode)
{
if(l>ar||r<al) return ;
int mid=(l+r)>>1;
if(l>=al&&r<=ar)
{
if(mode==1) T[R].fill(1);//根据操作方案，赋值
else T[R].fill(2,r-l+1);
return ;
}//更新
push_down(l,r,mid,R);//下放懒标记
updata(l,mid,al,ar,R<<1,mode);
updata(mid+1,r,al,ar,R<<1|1,mode);
push_up(l,r,mid,R);//合并
return ;
}
int check(int l,int r,int R,int m)
{
int mid=(l+r)>>1;
push_down(l,r,mid,R);
if(T[R].lmax>=m) return l;//左端点可以拓展出比m长的长度，直接返回
if(T[R<<1].Max>=m) return check(l,mid,R<<1,m);//左区间的最大值大于m，递归查找
if(T[R<<1].rmax+T[R<<1|1].lmax>=m) return mid-T[R<<1].rmax+1;//从中间向左右拓展是可以的，返回
if(T[R<<1|1].Max>=m) return check(mid+1,r,R<<1|1,m);//右区间查询
return 0;//无解
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
build(1,n,1);
int opt,x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&opt,&x);
if(opt==1)
{
int ans=check(1,n,1,x);
if(ans) updata(1,n,ans,ans+x-1,1,1);
printf("%d\n",ans);
}
else
{
scanf("%d",&y);
updata(1,n,x,min(n,x+y-1),1,2);
}
}
return 0;
}