[数据结构与算法]【LuoguP2894】HOTEL（线段树）

传送门

Description

???$n$个空房间，支持两种操作：

1、询问是否有连续$k$个空房间，若有返回最小起点，并将此k个连续空房间住满；

2、将一段区间内的房间变空。

Solution

???线段树维护区间最长连续空房间长度$val$，原理同维护最大子段和，需要维护每个区间从左端点起的最大连续空房间长度 $lsum$、从右端点起的最大连续空房间长度$rsum$。

???查询时若当前节点的$val>k$ ,说明一定有解。寻找最左边的起点时可分为三种情况：

（1）k个连续空房间全部位于左子树上，此时递归左子树；
（2）k个连续空房间 部分位于左子树上，部分位于右子树上，此时可以直接计算出起点并返回；
（3）k个连续空房间全部位于右子树上，此时递归右子树。

#include<bits/stdc++.h>
#define MAXN 50005
using namespace std;
inline int Fread(){
	int val=0;bool sign=false;char ch;
	while(~(ch=getchar()) && (ch<'0' || ch>'9') && (ch^'-'));
	val=(sign=!(ch^'-'))?0:ch^48;
	while(~(ch=getchar()) && (ch>='0' && ch<='9'))	val=(val<<1)+(val<<3)+(ch^48);
	return sign?~val+1:val;
}
int n,m;
struct Tree{
	int l,r,val,lsum,rsum,lazy;
}tr[MAXN<<3];
inline void push_up(int k){
	tr[k].lsum=tr[k<<1].lsum==tr[k<<1].r-tr[k<<1].l+1?tr[k<<1].lsum+tr[k<<1|1].lsum:tr[k<<1].lsum;
	tr[k].rsum=tr[k<<1|1].rsum==tr[k<<1|1].r-tr[k<<1|1].l+1?tr[k<<1].rsum+tr[k<<1|1].rsum:tr[k<<1|1].rsum;
	tr[k].val=max(max(tr[k<<1].val,tr[k<<1|1].val),tr[k<<1].rsum+tr[k<<1|1].lsum);
}
inline void push_down(int k){
	if(tr[k].lazy==1){
		tr[k<<1].lazy=tr[k<<1|1].lazy=1;
		tr[k<<1].lsum=tr[k<<1].rsum=tr[k<<1].val=tr[k<<1].r-tr[k<<1].l+1;
		tr[k<<1|1].rsum=tr[k<<1|1].lsum=tr[k<<1|1].val=tr[k<<1|1].r-tr[k<<1|1].l+1;
	}
	else{
		tr[k<<1].lazy=tr[k<<1|1].lazy=2;
		tr[k<<1].lsum=tr[k<<1].rsum=tr[k<<1].val=tr[k<<1|1].rsum=tr[k<<1|1].lsum=tr[k<<1|1].val=0;
	}
	tr[k].lazy=0;
}
void build(int k,int l,int r){
	tr[k].l=l,tr[k].r=r;
	if(l==r){
		tr[k].val=tr[k].lsum=tr[k].rsum=1;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
	push_up(k);
}
void update(int k,int l,int r,int tp){
	if(l<=tr[k].l && r>=tr[k].r){
		if(tp==1)	tr[k].lsum=tr[k].rsum=tr[k].val=tr[k].r-tr[k].l+1;
		else	tr[k].lsum=tr[k].rsum=tr[k].val=0;
		tr[k].lazy=tp;
		return;
	}
	if(tr[k].lazy)	push_down(k);
	int mid=tr[k].l+tr[k].r>>1;
	if(l<=mid)	update(k<<1,l,r,tp);
	if(r>mid)	update(k<<1|1,l,r,tp);
	push_up(k);
}
int query(int k,int x){
	if(tr[k].l==tr[k].r)	return tr[k].l;
	if(tr[k].lazy)	push_down(k);
	int mid=tr[k].l+tr[k].r>>1;
	if(tr[k<<1].val>=x)	return query(k<<1,x);
	if(tr[k<<1].rsum+tr[k<<1|1].lsum>=x)	return mid-tr[k<<1].rsum+1;
	return query(k<<1|1,x);
}
signed main(){
	n=Fread(),m=Fread();
	build(1,1,n);
	while(m--){
		int opt=Fread();
		if(opt==1){
			int x=Fread(),q=tr[1].val>=x?query(1,x):0;
			printf("%d\n",q);
			if(q)	update(1,q,q+x-1,2);
		}
		else{
			int x=Fread(),y=Fread();
			update(1,x,x+y-1,1);
		}
	}
	return 0;
} 

? ? ?最近做了点线段树，结果美团杯刚上来就把easy难度的数据结构给扔了，感谢队友还配合我表演了一会儿。昨晚看jls直播时听到罗国杰老师讲线段树的起源，感觉挺有趣的。看完直播心力憔悴鸽了cf，找了道题对着屏幕调了半天调出一堆sb错误，果然log2r只有三行码力thm不会变。
? ? ?多校前会出个Segtree相关的合集（咕咕），多校会更新解题和补题报告（kmm说的）。