添加 lsum[ ] , rsum[ ] , msum[ ] 来记录从左到右的区间，从右到左的区间和最大的区间；
#include<stdio.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 50005
int rsum[maxn<<],lsum[maxn<<],msum[maxn<<];//msum[]维护区间1…N中的最大连续区间长度
int mark[maxn<<];
int max(int x,int y)
{
return x>y?x:y;
}
void pushup(int l,int r,int rt)
{
int m=(l+r)/;
lsum[rt]=lsum[rt<<];
rsum[rt]=rsum[rt<<|];
msum[rt]=max(msum[rt<<],msum[rt<<|]);
if(lsum[rt<<]==m-l+)
lsum[rt]=lsum[rt<<]+lsum[rt<<|];
if(rsum[rt<<|]==r-m)
rsum[rt]=rsum[rt<<|]+rsum[rt<<];
msum[rt]=max(msum[rt],lsum[rt<<|]+rsum[rt<<]);
}
void pushdown(int l,int r,int rt)
{
if(mark[rt]!=-)
{
int len=r-l+; mark[rt<<]=mark[rt];
mark[rt<<|]=mark[rt];
if(mark[rt]==)
{
lsum[rt<<]=rsum[rt<<]=msum[rt<<]=;
lsum[rt<<|]=rsum[rt<<|]=msum[rt<<|]=;
}
else
{
lsum[rt<<]=rsum[rt<<]=msum[rt<<]=len-len/;
rsum[rt<<|]=lsum[rt<<|]=msum[rt<<|]=len/;
}
mark[rt]=-;
}
}
void build(int l,int r,int rt)
{
mark[rt]=-;
if(l==r)
{
lsum[rt]=rsum[rt]=msum[rt]=;
return ;
}
int m=(l+r)/;
build(lson);
build(rson);
pushup(l,r,rt);
}
void updata(int L,int R,int c,int l,int r,int rt)
{
if(l>=L&&R>=r)
{
mark[rt]=c;
if(mark[rt]==)
{
lsum[rt]=rsum[rt]=msum[rt]=;
}
else
lsum[rt]=rsum[rt]=msum[rt]=r-l+;
return ;
}
pushdown(l,r,rt);
int m=(l+r)/;
if(m>=L)
updata(L,R,c,lson);
if(R>m)
updata(L,R,c,rson);
pushup(l,r,rt);
}
int query(int num,int l,int r,int rt)
{
if(l==r)
{
return l;
}
pushdown(l,r,rt);
int m=(l+r)/;
int ret;
if(msum[rt<<]>=num)//由于从最左边开始坐位子，所以rsum[rt<<1]>
{
return query(num,lson);
}
else if(lsum[rt<<|]+rsum[rt<<]>=num)
return m-rsum[rt<<]+;
else
return query(num,rson);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(,n,);
int a,b,c;
while(m--)
{
scanf("%d",&a);
if(a==)
{
scanf("%d",&b);
if(b>msum[])
printf("0\n");
else
{
int ret=query(b,,n,);
printf("%d\n",ret);
updata(ret,ret+b-,,,n,);
}
}
else
{
scanf("%d%d",&b,&c);
updata(b,b+c-,,,n,);
}
}
}
}