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<<];
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+;
x[a].la=-;
if(l==r)
return ;
int mid=(l+r)>>;
Build(l,mid,a<<);
Build(mid+,r,a<<|);
}
void push_down(int a)
{
int ll=x[a<<].r-x[a<<].l+;
int rr=x[a<<|].r-x[a<<|].l+;
x[a<<].la=x[a<<|].la=x[a].la;
x[a<<].rsum=x[a<<].lsum=x[a<<].msum=x[a].la?:ll;
x[a<<|].rsum=x[a<<|].lsum=x[a<<|].msum=x[a].la?:rr;
x[a].la=-;
}
void push_up(int a)
{
int ll=x[a<<].r-x[a<<].l+;
int rr=x[a<<|].r-x[a<<|].l+;
x[a].lsum=x[a<<].lsum;
if(x[a].lsum==ll)//区间合并
x[a].lsum+=x[a<<|].lsum;
x[a].rsum=x[a<<|].rsum;
if(x[a].rsum==rr)
x[a].rsum+=x[a<<].rsum;
x[a].msum=max(max(x[a<<].msum,x[a<<|].msum),x[a<<].rsum+x[a<<|].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?:(r-l+);
x[a].la=w;
return ;
}
int mid=(l+r)>>;
if(x[a].la!=-)
push_down(a);
if(a1<=mid)
update(l,mid,a1,b1,w,a<<);
if(b1>mid)
update(mid+,r,a1,b1,w,a<<|);
push_up(a);
}
int Ques(int l,int r,int w,int a)
{
if(l==r)
return l;
if(x[a].la!=-)
push_down(a);
int mid=(l+r)>>;
if(x[a<<].msum>=w)//左孩子最大连续区间够了
return Ques(l,mid,w,a<<);
else if(x[a<<].rsum+x[a<<|].lsum>=w)//中间连续够了
return mid-x[a<<].rsum+;
return Ques(mid+,r,w,a<<|); //右边
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
Build(,n,);
while(m--)
{
int op,a,b;
scanf("%d",&op);
if(op==)
{
scanf("%d",&a);
if(x[].msum<a)//最大的
printf("0\n");
else
{
int p=Ques(,n,a,);
printf("%d\n",p);
update(,n,p,p+a-,,);//变成使用
}
}
else
{
scanf("%d%d",&a,&b);
update(,n,a,a+b-,,);//变成未使用
}
}
return ;
}