题解：和基础的线段树操作差别不是很大，就是在传统的线段树基础上多维护一段区间最长的合法前驱（h_），最长合法后驱（t_），一段中最长的合法区间（mx）。询问时由于查询的是最左边的合法端点，所以要从左到中间到右边依次考虑情况。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int maxn=+,maxm=+;
int N,M,o,D,X,ans;
inline int rd(){
int x=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
struct Tree{
int l,r,lazy,h_,t_,mx;
}t[maxn<<];
inline void Pushup(int x){
int ls=x<<,rs=x<<|;
if(t[ls].r-t[ls].l+==t[ls].mx)t[x].h_=t[ls].mx+t[rs].h_;else t[x].h_=t[ls].h_;
if(t[rs].r-t[rs].l+==t[rs].mx)t[x].t_=t[rs].mx+t[ls].t_;else t[x].t_=t[rs].t_;
t[x].mx=max(t[ls].mx,t[rs].mx);
t[x].mx=max(t[x].mx,t[ls].t_+t[rs].h_);
return;
}
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;t[x].lazy=-;
if(l==r){
t[x].h_=t[x].t_=t[x].mx=;
return;
}
int mid=(l+r)>>;
Build(x<<,l,mid);Build(x<<|,mid+,r);
Pushup(x);
return;
}
inline void Pushdown(int x){
if(t[x].lazy>=){
int k=t[x].lazy,ls=x<<,rs=x<<|;t[x].lazy=-;
if(k==){
t[ls].h_=t[ls].t_=t[ls].mx=;
t[rs].h_=t[rs].t_=t[rs].mx=;
}
else{
t[ls].h_=t[ls].t_=t[ls].mx=t[ls].r-t[ls].l+;
t[rs].h_=t[rs].t_=t[rs].mx=t[rs].r-t[rs].l+;
}
t[ls].lazy=t[rs].lazy=k;
}
return;
}
inline int Solve(int x,int d){
int ls=x<<,rs=x<<|,l=t[x].l,r=t[x].r;
if(r-l+==t[x].mx&&t[x].mx==d)return l;
Pushdown(x);
if(t[ls].mx>=d)return Solve(ls,d);
if(t[ls].t_+t[rs].h_>=d)return (t[ls].r-t[ls].t_+);
if(t[rs].mx>=d)return Solve(rs,d);
return ;
}
inline void Update(int x,int ql,int qr,int o){
int l=t[x].l,r=t[x].r;
if(ql<=l&&r<=qr){
if(o==)t[x].h_=t[x].t_=t[x].mx=;
else t[x].h_=t[x].t_=t[x].mx=r-l+;
t[x].lazy=o;
return;
}
int mid=(l+r)>>,ls=x<<,rs=x<<|;
Pushdown(x);
if(ql<=mid)Update(ls,ql,qr,o);
if(qr>mid)Update(rs,ql,qr,o);
Pushup(x);
return;
}
inline void write(int x){
char a[];int len=;
for(;x;x/=)a[len++]=x%;
if(!len)putchar('');
else while(len)putchar(a[--len]+'');
putchar('\n');
}
int main(){
N=rd();M=rd();
Build(,,N);
while(M--){
o=rd();
if(o==){
D=rd();
ans=Solve(,D);
write(ans);
if(ans)Update(,ans,ans+D-,);//1表示有住人
}
else{
X=rd();D=rd();
Update(,X,X+D-,);
}
}
return ;
}
//我为了卡常加入了快速读入和快速输出，实际食用代码时完全可以无视。
By：AlenaNuna