题意

第一行输入 $n,m$，$n$ 代表有 $n$ 个房间 $(1\le n\le 50000)$，编号为 $1\sim n$，开始都为空房，$m$ 表示以下有 $m$ 行操作 $(1\le m<50000)$，以下每行先输入一个数 $op$ ，表示一种操作：

若 $op$ 为 $1$ 表示查询房间，再输入一个数 $x$，表示在 $1,2,...,n$ 房间中找到长度为 $x$ 的连续空房，输出连续 $x$ 个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为 $x$ 的连续空房，输出 $0$。若找得到，在这 $x$ 个空房间中住上人。

若 $op$ 为 $2$ 表示退房，再输入两个数 $x,y$ 代表房间号 $x\sim x+y-1$ 退房，即让房间为空。

你需要对每个输入 $1$ 输出对应的答案。

思路

目标是要维护区间内最长的连续的 $0$ 的数量。典型地，我们可以维护：

1. $lma$：区间左端起最大段连续 $0$；
2. $rma$：区间右端起最大连续段 $0$；
3. $ma$：区间的最大段连续 $0$。

对于 pushup 操作就是取左子区间的 $lma$、右子区间的 $rma$ 和左子区间的 $rma$ 加右子区间的 $lma$，给一幅图就很清晰了：

对于该区间的 $lma$，按理来说是取 $ls$ 的 $lma$。但是如果当 $ls$ 的 $lma$ 占据了整个 $ls$、连上了 $rs$ 的 $lma$，就可以拓展这一贡献；对于该区间的 $rma$ 同样如此。

void pushup(ll u)
{
	T[u].ma=max(max(T[ls].ma,T[rs].ma),T[ls].rma+T[rs].lma);
	T[u].lma=max(T[ls].lma,(T[ls].ma==T[ls].len?T[ls].ma+T[rs].lma:0ll));
	T[u].rma=max(T[rs].rma,(T[rs].ma==T[rs].len?T[rs].ma+T[ls].rma:0ll)); 
}

其中 $len$ 是区间长度，build 时维护即可。

对于区间的入住与退房处理，可以使用懒标记节省时间，那么下面讲标记下放 pushdown 怎么处理。

懒标记 $tag$，$tag=1$ 表示一段区间的入住，入住则整一段区间没有空房了，此时本区间和左右子区间的 $lma$、$rma$、$ma$ 都为$0$。

$tag=2$ 表示一段区间的退房，退房则整一段区间都是空房，此时本区间和左右子区间的 $lma$、$rma$、$ma$ 都为对应区间长度。

然后就是基本的标记下放，顺便把入住和退房的函数写了：

void pushdown(ll u)
{
	if(T[u].tag)
	{
		if(T[u].tag==1)
		{
			T[ls].ma=T[ls].lma=T[ls].rma=0;
			T[rs].ma=T[rs].lma=T[rs].rma=0;
		}
		else 
		{
			T[ls].ma=T[ls].lma=T[ls].rma=T[ls].len;
			T[rs].ma=T[rs].lma=T[rs].rma=T[rs].len;
		}
		T[ls].tag=T[u].tag,T[rs].tag=T[u].tag;
		T[u].tag=0;
	}
}

//book:预定 leave:退房
void book(ll u,ll l,ll r,ll ql,ll qr)
{
	if(qr<l||r<ql)return;
	if(ql<=l&&r<=qr)
	{
		T[u].ma=T[u].lma=T[u].rma=0;
		T[u].tag=1;
		return;
	}
	pushdown(u);
	ll mid=(l+r)>>1;
	if(ql<=mid)book(ls,l,mid,ql,qr);
	if(qr>mid)book(rs,mid+1,r,ql,qr);
	pushup(u);
}
void leav(ll u,ll l,ll r,ll ql,ll qr)
{
	if(qr<l||r<ql)return;
	if(ql<=l&&r<=qr)
	{
		T[u].ma=T[u].lma=T[u].rma=T[u].len;
		T[u].tag=2;
		return;
	}
	pushdown(u);
	ll mid=(l+r)>>1;
	if(ql<=mid)leav(ls,l,mid,ql,qr);
	if(qr>mid)leav(rs,mid+1,r,ql,qr);
	pushup(u); 
}

接下来是查询操作，我们要找编号最小的，能够塞得下连续$x$个人的空房区间，向下查询需要按照编号尽量小的优先顺序分别对左子区间$ls$、中间段、右子区间$rs$进行查找。要注意，找的是编号尽量小而不是空余区间尽量长的。

1. 如果左子区间 $ls$ 的 $ma$ 可以塞得下 $x$，那么就往左子区间找；
2. 如果中间段可以满足，即 $ls$ 的 $rma$ 加 $rs$ 的 $lma$ 可以塞得下 $x$，那么答案就是 $ls$ 的 $rma$ 的开始处，可以直接算出来的，就是 $mid-T[ls].rma+1$；
3. 如果右子区间可以满足，与 1 同理；
4. 剩下没有的，直接返回 $0$ 就好了。

ll query(ll u,ll l,ll r,ll len)
{
	if(l>r||T[u].ma<len)return 0;
	if(l==r)return l;
	pushdown(u);
	ll mid=(l+r)>>1;
	if(T[ls].ma>=len)return query(ls,l,mid,len);
	else if(T[ls].rma+T[rs].lma>=len)return mid-T[ls].rma+1;
	else if(T[rs].ma>=len)return query(rs,mid+1,r,len);
	else return 0;
}

最后提醒一句，当没有满足条件的空房间区间，输出 $0$ 之后，一定要直接$continue$，不然就会不小心把 $0$ 之后的房间填满。

具体细节见代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const int N=5e4+9,M=20;
ll n,m;
struct SegT
{
	struct node
	{
		ll lma,rma,ma;//左右端最大连续0，区间最多连续0
		ll tag,len;
	}T[N<<2];
	void pushup(ll u)
	{
		T[u].ma=max(max(T[ls].ma,T[rs].ma),T[ls].rma+T[rs].lma);
		T[u].lma=max(T[ls].lma,(T[ls].ma==T[ls].len?T[ls].ma+T[rs].lma:0ll));
		T[u].rma=max(T[rs].rma,(T[rs].ma==T[rs].len?T[rs].ma+T[ls].rma:0ll)); 
	}
	void pushdown(ll u)
	{
		if(T[u].tag)
		{
			if(T[u].tag==1)
			{
				T[ls].ma=T[ls].lma=T[ls].rma=0;
				T[rs].ma=T[rs].lma=T[rs].rma=0;
			}
			else 
			{
				T[ls].ma=T[ls].lma=T[ls].rma=T[ls].len;
				T[rs].ma=T[rs].lma=T[rs].rma=T[rs].len;
			}
			T[ls].tag=T[u].tag,T[rs].tag=T[u].tag;
			T[u].tag=0;
		}
	}
	void build(ll u,ll l,ll r)
	{
		T[u].ma=T[u].lma=T[u].rma=T[u].len=r-l+1;
		if(l==r)return;
		ll mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(u);
	}
	void book(ll u,ll l,ll r,ll ql,ll qr)
	{
		if(qr<l||r<ql)return;
		if(ql<=l&&r<=qr)
		{
			T[u].ma=T[u].lma=T[u].rma=0;
			T[u].tag=1;
			return;
		}
		pushdown(u);
		ll mid=(l+r)>>1;
		if(ql<=mid)book(ls,l,mid,ql,qr);
		if(qr>mid)book(rs,mid+1,r,ql,qr);
		pushup(u);
	}
	void leav(ll u,ll l,ll r,ll ql,ll qr)
	{
		if(qr<l||r<ql)return;
		if(ql<=l&&r<=qr)
		{
			T[u].ma=T[u].lma=T[u].rma=T[u].len;
			T[u].tag=2;
			return;
		}
		pushdown(u);
		ll mid=(l+r)>>1;
		if(ql<=mid)leav(ls,l,mid,ql,qr);
		if(qr>mid)leav(rs,mid+1,r,ql,qr);
		pushup(u); 
	}
	ll query(ll u,ll l,ll r,ll len)
	{
		if(l>r||T[u].ma<len)return 0;
		if(l==r)return l;
		pushdown(u);
		ll mid=(l+r)>>1;
		if(T[ls].ma>=len)return query(ls,l,mid,len);
		else if(T[ls].rma+T[rs].lma>=len)return mid-T[ls].rma+1;
		else if(T[rs].ma>=len)return query(rs,mid+1,r,len);
		else return 0;
	}
}A;
int main()
{
	scanf("%lld%lld",&n,&m);
	A.build(1,1,n);
	while(m--)
	{
		ll op,l;
		scanf("%lld%lld",&op,&l);
		if(op==1)
		{
			ll st=A.query(1,1,n,l);
			printf("%lld\n",st);
			if(st)A.book(1,1,n,st,st+l-1);
		}
		else 
		{
			ll r;
			scanf("%lld",&r);
			r=r+l-1;
			A.leav(1,1,n,l,r);
		}
	}
	return 0;
}