Hotel（思维 + 线段树 + 懒标记）（查询变种）

题目链接

这个好难…线段树变种…

题目描述：

奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50,000)间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的湖面。

贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台，希望能订到D_i (1 <= D_i <= N)间连续的房间。服务台的接待工作也很简单：如果存在r满足编号为r…r+D_i-1的房间均空着，他就将这一批顾客安排到这些房间入住；如果没有满足条件的r，他会道歉说没有足够的空房间，请顾客们另找一家宾馆。如果有多个满足条件的r，服务员会选择其中最小的一个。

旅馆中的退房服务也是批量进行的。每一个退房请求由2个数字X_i、D_i描述，表示编号为X_i…X_i+D_i-1 (1 <= X_i <= N-D_i+1)房间中的客人全部离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。

而你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共需要处理M (1 <= M < 50,000)个按输入次序到来的住店或退房的请求。第一个请求到来前，旅店中所有房间都是空闲的。

分析

思路参考于这里的代码：

修改操作操作其实很简单，就是一个区间置为1 和 区间置为0，这个搞一个懒标记就行了;

关键是这个查询操作，每次要找到满足条件的最小的一个点…

那么问题就转换成了要维护什么信息使得每次能够查询出满足条件的最小点？以及怎么维护？

直接上答案吧，真的不好想…

我们规定0表示没被占，1表示被占；

开一个线段树维护区间内连续的0的个数：前缀连续个数pre，后缀连续个数ne，最大连续个数mx；

然后我们对查询函数变种一下（其实个人感觉有点像树上二分），假设当前要查询连续d个0；

if 左子节点的mx >= d，则说明左边有满足的，那么直接递归左边去；否则说明左边找不到了。

else if 左子节点的ne + 右子节点的pre >= d，说明两个子区间合并就满足了，那么我们可以直接算出这个点，mid-ne+1;

else 一定出现在右边，直接递归右边就行。

这样我们就找到答案了…

下面就是怎么维护的问题了…

这个就比较简单了, 前置题目看这里：https://www.acwing.com/problem/content/246/

分别考虑pushup、pushdown、打懒标记 时各种信息怎么维护就行

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include <unordered_map>
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second
  
#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)

typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;
 
const int maxn = 1e5 + 7;
const int N = 2010 + 7;
const int M = 1e6 + 7;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
// const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

struct node
{
	int l,r;
	
	int pre;	//前缀
	int ne;		//后缀
	int mx;		//最大连续
	
	int add;	//懒标记
	
}tr[maxn*4];

int n,m;

void pushup(int u)
{
	int ls = tr[u<<1].r - tr[u<<1].l + 1;
	int rs = tr[u<<1|1].r - tr[u<<1|1].l + 1;
	
	tr[u].mx = max(tr[u<<1].ne + tr[u<<1|1].pre, max(tr[u<<1].mx,tr[u<<1|1].mx));
	tr[u].pre = tr[u<<1].pre + (ls == tr[u<<1].pre ? tr[u<<1|1].pre : 0);
	tr[u].ne = tr[u<<1|1].ne + (rs == tr[u<<1|1].ne ? tr[u<<1].ne : 0);
}

void pushdown(int u)
{
	int ls = tr[u<<1].r - tr[u<<1].l + 1;
	int rs = tr[u<<1|1].r - tr[u<<1|1].l + 1;
	
	if(tr[u].add != -1)
	{
		tr[u<<1].add = tr[u].add;
		tr[u<<1].mx = tr[u<<1].pre = tr[u<<1].ne = (tr[u].add == 0 ? ls : 0);
		
		tr[u<<1|1].add = tr[u].add;
		tr[u<<1|1].mx = tr[u<<1|1].pre = tr[u<<1|1].ne = (tr[u].add == 0 ? rs : 0);	
		
		tr[u].add = -1;
	}
}

void build(int u,int l,int r)
{
	if(l == r)
	{
		tr[u] = {l,r,1,1,1,-1};
		return;
	}
	
	tr[u] = {l,r};
	tr[u].add = -1;
	
	int mid = l + r >> 1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	pushup(u);
}

void update(int u,int l,int r,int flag)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].mx = tr[u].pre = tr[u].ne = (flag == 0 ? (tr[u].r-tr[u].l+1) : 0);
		tr[u].add = flag;
		
		return;
	}
	
	pushdown(u);

	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) update(u<<1, l, r, flag);
	if(r > mid) update(u<<1|1, l, r, flag);
	
	pushup(u);	
}

int query(int u,int d)
{
	if(tr[u].l == tr[u].r) return tr[u].l;
	
	pushdown(u);
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	if(tr[u<<1].mx >= d) return query(u<<1,d);
	else if(tr[u<<1].ne + tr[u<<1|1].pre >= d) return mid-tr[u<<1].ne+1;
	else return query(u<<1|1,d);
}

int main()
{
	iire(n,m);
	build(1,1,n);
	
	while(m--)
	{
		int op;
		ire(op);
		
		if(op == 1)
		{
			int d;
			ire(d);		
			
			if(tr[1].mx < d) cout<<0<<'\n';
			else
			{
				int ans = query(1,d);
				cout<<ans<<'\n';
				
				update(1,ans,ans+d-1,1);	//区间置为1
			}
		}
		else	//退房
		{
			int x,d;
			iire(x,d);
			
			update(1,x,x+d-1,0);	//区间置为0
		}
	}
	
	return 0;
}