洛谷 P2894 USACO08FEB Hotel 题解

题意

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

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

若 $iop为 $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)); 
}

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

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

$tag=2$表示一段区间的退房，退房则整一段区间都是空房，此时本区间和左右子区间的$lma$、$rma$、$ma$都为对应区间长度。（因此为了方便，可以再维护一个子区间长度$len$）

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

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$之后的房间填满qwq。

#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;
}