用线段树维护三个值：区间最长空位长度，从左端点可以延伸的最长空位长度，从右端点可以延伸的最长空位长度。
#include<complex>
#include<cstdio>
using namespace std;
const int N=2e6+;
int n,m;
int len[N],Max[N],maxl[N],maxr[N],lazy[N];
int qread()
{
int x=;
char ch=getchar();
while(ch<'' || ch>'')ch=getchar();
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
void PushUp(int rt)
{
if(Max[rt<<]==len[rt<<])maxl[rt]=Max[rt<<]+maxl[rt<<|];
else maxl[rt]=maxl[rt<<];
if(Max[rt<<|]==len[rt<<|])maxr[rt]=Max[rt<<|]+maxr[rt<<];
else maxr[rt]=maxr[rt<<|];
Max[rt]=max(max(Max[rt<<],Max[rt<<|]),maxr[rt<<]+maxl[rt<<|]);
}
void PushDown(int rt)
{
if(!lazy[rt])return;
lazy[rt<<]=lazy[rt<<|]=lazy[rt];
if(lazy[rt]==)
{
Max[rt<<]=maxl[rt<<]=maxr[rt<<]=;
Max[rt<<|]=maxl[rt<<|]=maxr[rt<<|]=;
}
else
{
Max[rt<<]=maxl[rt<<]=maxr[rt<<]=len[rt<<];
Max[rt<<|]=maxl[rt<<|]=maxr[rt<<|]=len[rt<<|];
}
lazy[rt]=;
}
void Build(int l,int r,int rt)
{
maxl[rt]=maxr[rt]=Max[rt]=len[rt]=r-l+;
if(l==r)return;
int mid=l+r>>;
Build(l,mid,rt<<);Build(mid+,r,rt<<|);
}
void Modify(int l,int r,int rt,int nowl,int nowr,int v)
{
if(nowl<=l && r<=nowr)
{
if(v==)Max[rt]=maxl[rt]=maxr[rt]=;
else Max[rt]=maxl[rt]=maxr[rt]=len[rt];
lazy[rt]=v;
return;
}
PushDown(rt);
int mid=l+r>>;
if(nowl<=mid)Modify(l,mid,rt<<,nowl,nowr,v);
if(mid<nowr)Modify(mid+,r,rt<<|,nowl,nowr,v);
PushUp(rt);
}
int Query(int l,int r,int rt,int p)
{
if(l==r)return l;
PushDown(rt);
int mid=l+r>>;
if(Max[rt<<]>=p)return Query(l,mid,rt<<,p);
if(maxr[rt<<]+maxl[rt<<|]>=p)return mid-maxr[rt<<]+;
return Query(mid+,r,rt<<|,p);
}
int main()
{
scanf("%d%d",&n,&m);
Build(,n,);
int p,l,r,x;
while(m--)
{
p=qread();
if(p==)
{
x=qread();
if(Max[]<x){puts("");continue;}
int tot=Query(,n,,x);
printf("%d\n",tot);
Modify(,n,,tot,tot+x-,);
}
else
{
l=qread();r=qread();
Modify(,n,,l,l+r-,);
}
}
return ;
}