题很简单：给两个操作1：查找最左边的a个空余块并填满
2：把从第a个开始的连续b个块置空
线段树维护左连续，右连续，最大连续，lazy-tag即可，query函数值得学习
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 500005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int lmx[maxn<<],rmx[maxn<<],mx[maxn<<],flag[maxn<<]; inline void set0(int l,int r,int rt){
lmx[rt]=rmx[rt]=mx[rt]=r-l+;
flag[rt]=;
}
inline void set1(int l,int r,int rt){
lmx[rt]=rmx[rt]=mx[rt]=;
flag[rt]=;
}
inline void pushup(int l,int r,int rt){
lmx[rt]=lmx[rt<<];rmx[rt]=rmx[rt<<|];
mx[rt]=max(mx[rt<<],mx[rt<<|]);
int m=l+r>>;
if(lmx[rt<<]==m-l+) lmx[rt]+=lmx[rt<<|];
if(rmx[rt<<|]==r-m) rmx[rt]+=rmx[rt<<];
if(rmx[rt<<]&&lmx[rt<<|])
mx[rt]=max(mx[rt],rmx[rt<<]+lmx[rt<<|]); }
inline void pushdown(int l,int r,int rt){
if(flag[rt]>=){
int m=l+r>>;
flag[rt<<]=flag[rt<<|]=flag[rt];
if(flag[rt]==){
set0(lson);set0(rson);
}
else if(flag[rt]==){
set1(lson);set1(rson);
}
flag[rt]=-;
}
}
void build(int l,int r,int rt){
if(l==r){
lmx[rt]=rmx[rt]=mx[rt]=;
flag[rt]=-;
return;
}
int m=l+r>>;
build(lson);
build(rson);
pushup(l,r,rt);
}
void update(int L,int R,int op,int l,int r,int rt){
if(L<=l && R>=r){
if(op==) set0(l,r,rt);
if(op==) set1(l,r,rt);
return;
}
pushdown(l,r,rt);
int m=l+r>>;
if(L<=m)
update(L,R,op,lson);
if(R>m)
update(L,R,op,rson);
pushup(l,r,rt);
}
//cnt要么在左儿子，要么在中间合并块，要么在右子树
int query(int cnt,int l,int r,int rt){
if(l==r)
return l;
pushdown(l,r,rt);
int m=l+r>>;
if(cnt<=mx[rt<<])
return query(cnt,lson);
else if(cnt<=rmx[rt<<]+lmx[rt<<|])
return m-rmx[rt<<]+;
else
return query(cnt,rson);
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)==){
build(,n,); int a,b,op;
while(m--){
scanf("%d",&op);
if(op==){
scanf("%d",&a);
if(mx[]<a){
puts("");
continue;
}
int tmp=query(a,,n,);
printf("%d\n",tmp);
update(tmp,tmp+a-,,,n,);
}
else if(op==){
scanf("%d%d",&a,&b);
update(a,a+b-,,,n,);
}
}
}
return ;
}