这道题是道线段树的好题，值得一做

为什么说是道线段树好题呢，因为它不拘于线段树的模板，在查询部分非常毒瘤有趣。

回到正题，看到区间操作，容易想到线段树维护。

和维护区间最大子段和相似，存储最大连续空房，最大前缀空房和最大后缀空房。

还有一点：tagtag有三种值，代表区间退房（22），区间入住（11），没有tagtag（00）

值得注意的是pushuppushup操作和pushdownpushdown操作（其他和普通线段树一样）

code:code:（pushuppushup操作和pushdownpushdown操作）

void up(int root){
	a[root].lm=a[ls].lm;
	a[root].rm=a[rs].rm;
	a[root].sum=max(max(a[ls].sum,a[rs].sum),a[ls].rm+a[rs].lm);//sum只有三种可能：只包含左孩子，横跨左右孩子，只包含右孩子
	if(a[ls].sum==a[ls].len)
		a[root].lm=a[ls].sum+a[rs].lm;
	if(a[rs].sum==a[rs].len)
		a[root].rm=a[rs].sum+a[ls].rm;//最大前缀空房和最大后缀空房
	return;
}
void pd(int root){
	if(!a[root].tag)return;
	if(a[root].tag==1){
		a[ls].sum=0;a[ls].lm=0;a[ls].rm=0;a[ls].tag=1;
		a[rs].sum=0;a[rs].lm=0;a[rs].rm=0;a[rs].tag=1;//区间入住，全置0
	}
	else{
		a[ls].sum=a[ls].len;a[ls].lm=a[ls].len;
		a[ls].rm=a[ls].len;a[ls].tag=2;
		a[rs].sum=a[rs].len;a[rs].lm=a[rs].len;
		a[rs].rm=a[rs].len;a[rs].tag=2;//区间退房，全置len
	}
	a[root].tag=0;
}

还有一个重点（也是个人认为的本体最难点）：queryquery怎么写？

其实这里的queryquery已经不太像线段树的queryquery了

对于每次查询到的节点，如果左孩子有足够空房就递归到左孩子，否则横跨两个孩子，然后再递归右孩子。

code:code:

int query(int root,int l,int r,int k){
	pd(root);
	if(a[root].sum<k)return 0;
	if(a[ls].sum>=k)return query(ls,l,mid,k);//左孩子
	if(a[ls].rm+a[rs].lm>=k)return mid-a[ls].rm+1;//横跨
	if(a[rs].sum>=k)return query(rs,mid+1,r,k);//右孩子
}

所有的难点都攻克了，除此以外，还要注意：

  • 别直接用cincin
  • 记得pushdownpushdown和pushuppushup
  • 别把lsls和rsrs弄混

最后就是完整代码了~

#include<iostream>
using namespace std;
#define ls (root<<1)
#define rs (root<<1|1)
#define mid ((l+r)>>1)
struct point{
	int sum,lm,rm,len,tag;
} a[400005];
void up(int root){
	a[root].lm=a[ls].lm;
	a[root].rm=a[rs].rm;
	a[root].sum=max(max(a[ls].sum,a[rs].sum),a[ls].rm+a[rs].lm);//sum只有三种可能：只包含左孩子，横跨左右孩子，只包含右孩子
	if(a[ls].sum==a[ls].len)
		a[root].lm=a[ls].sum+a[rs].lm;
	if(a[rs].sum==a[rs].len)
		a[root].rm=a[rs].sum+a[ls].rm;//最大前缀空房和最大后缀空房
	return;
}
void pd(int root){
	if(!a[root].tag)return;
	if(a[root].tag==1){
		a[ls].sum=0;a[ls].lm=0;a[ls].rm=0;a[ls].tag=1;
		a[rs].sum=0;a[rs].lm=0;a[rs].rm=0;a[rs].tag=1;//区间入住，全置0
	}
	else{
		a[ls].sum=a[ls].len;a[ls].lm=a[ls].len;
		a[ls].rm=a[ls].len;a[ls].tag=2;
		a[rs].sum=a[rs].len;a[rs].lm=a[rs].len;
		a[rs].rm=a[rs].len;a[rs].tag=2;//区间退房，全置len
	}
	a[root].tag=0;
}
void build(int root,int l,int r){
	a[root].len=r-l+1;a[root].sum=a[root].len;
	a[root].lm=a[root].len;a[root].rm=a[root].len;//简单初始化
	a[root].tag=0;
	if(l==r)return;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void change1(int root,int l,int r,int ql,int qr){//入住 
	pd(root);
	if(ql<=l&&qr>=r){//打tag
		a[root].tag=1;
		a[root].sum=0;a[root].lm=0;a[root].rm=0;
		return;
	}
	if(ql<=mid)change1(ls,l,mid,ql,qr);//递归左孩子
	if(qr>mid)change1(rs,mid+1,r,ql,qr);//递归右孩子
	up(root);
	return;
}
void change2(int root,int l,int r,int ql,int qr){//退房 
	pd(root);
	if(ql<=l&&qr>=r){//打tag
		a[root].sum=a[root].len;a[root].lm=a[root].len;
		a[root].rm=a[root].len;a[root].tag=2;
		return;
	}
	if(ql<=mid)change2(ls,l,mid,ql,qr);//递归左孩子
	if(qr>mid)change2(rs,mid+1,r,ql,qr);//递归右孩子
	up(root);
	return;
}
int query(int root,int l,int r,int k){
	pd(root);
	if(a[root].sum<k)return 0;
	if(a[ls].sum>=k)return query(ls,l,mid,k);//左孩子
	if(a[ls].rm+a[rs].lm>=k)return mid-a[ls].rm+1;//横跨
	if(a[rs].sum>=k)return query(rs,mid+1,r,k);//右孩子
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int n,m,opt,x,y,t;
	cin>>n>>m;
	build(1,1,n);
	for(int i=0;i<m;i++){
		cin>>opt;
		if(opt==1){
			cin>>x;
			t=query(1,1,n,x);
			cout<<t<<endl;
			if(t)change1(1,1,n,t,t+x-1);
		}
		else{
			cin>>x>>y;
			change2(1,1,n,x,x+y-1);
		}
	}
	return 0;
}