『线段树』「USACO月赛」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：询问是否存在一段连续的长度为$d$的空位置；若存在，则输出这个起点并将序列填满，且需要保证起点最小；若不存在，输出$0$.
• 询问2：将$[X,X+D?1]$的数去掉。

题解

一个用线段树维护的题，可以线段树练习的还不够自己写不出来。

初始化：维护每一个区间靠左的连续空位，靠右的连续空位，最大的连续空位。初始化的每一个值都是当前序列的长度。

修改操作：维护两个标记，一个表示开房操作，一个表示退房操作。主要在于spread函数和updata函数上。每一个点完全覆盖以后需要对子节点进行一次完全覆盖,即spread函数的作用；uptata函数和最长连续子段和相似；注意需要判断子区间是否完全覆盖，若不完全覆盖只能只用某一个区间的答案，若完全覆盖则可以全部加起来。

代码是这样的：

void updata(int p)
{
    if (a[p*2].max == a[p*2].len) a[p].lmax = a[p*2].len+a[p*2+1].lmax;else a[p].lmax = a[p*2].lmax;if (a[p*2+1].max == a[p*2+1].len) a[p].rmax = a[p*2].rmax+a[p*2+1].len;else a[p].rmax = a[p*2+1].rmax;a[p].max = max(a[p*2].rmax+a[p*2+1].lmax, max(a[p*2].max, a[p*2+1].max));return;
}

**查询操作：**分成3种：

• 左区间已经包括了答案的→查询左区间。
• 左区间的$rmax$和右区间的$lmax$构成答案的→找到左区间形成$rmax$序列的起始点，即$r?rmax+1.$
• 右区间已经包括答案的→查询右区间。
• 在查询之前记得特判一下是否有解。

代码如下：

#include <bits/stdc++.h>using namespace std;int n,m;struct SegmentTree {
    int l,r,len,max,lmax,rmax,tag;
} a[1000000];
int cnt = 0;
int Ans[200000];inline int read(void)
{
    int s = 0, w = 1;char c = getchar();while (c<'0' || c>'9') {
    if (c == '-') w = -1; c = getchar();}while (c>='0' && c<='9') s = s*10+c-48,c = getchar();return s*w;
}void build(int p,int l,int r)
{
    a[p].l = l;a[p].r = r;a[p].len = r-l+1;a[p].lmax = a[p].rmax = a[p].max = a[p].len;if (l == r) return;int mid = l+r >> 1;build(p*2,l,mid);build(p*2+1,mid+1,r);return;
}void spread(int p)
{
    if (a[p].tag == 0) return;if (a[p].tag == 1){
    a[p*2].tag = a[p*2+1].tag = 1;a[p*2].lmax = a[p*2].rmax = a[p*2].max = 0;a[p*2+1].lmax = a[p*2+1].rmax = a[p*2+1].max = 0;}if (a[p].tag == 2){
    a[p*2].tag = a[p*2+1].tag = 2;a[p*2].lmax = a[p*2].rmax = a[p*2].max = a[p*2].len;a[p*2+1].lmax = a[p*2+1].rmax = a[p*2+1].max = a[p*2+1].len;}a[p].tag = 0;return;
}void updata(int p)
{
    if (a[p*2].max == a[p*2].len) a[p].lmax = a[p*2].len+a[p*2+1].lmax;else a[p].lmax = a[p*2].lmax;if (a[p*2+1].max == a[p*2+1].len) a[p].rmax = a[p*2].rmax+a[p*2+1].len;else a[p].rmax = a[p*2+1].rmax;a[p].max = max(a[p*2].rmax+a[p*2+1].lmax, max(a[p*2].max, a[p*2+1].max));return;
}void change(int p,int l,int r,int tag)
{
    if (l <= a[p].l && r >= a[p].r){
    if (tag == 2) a[p].lmax = a[p].rmax = a[p].max = a[p].len;//退房if (tag == 1) a[p].lmax = a[p].rmax = a[p].max = 0;//开房a[p].tag = tag; return;}spread(p);int mid = a[p].l+a[p].r >> 1;if (l <= mid) change(p*2,l,r,tag);if (r > mid) change(p*2+1,l,r,tag);updata(p);return;
}int ask(int p,int d)
{
    spread(p);if (a[p].l == a[p].r) return a[p].l;if (a[p*2].max >= d) return ask(p*2,d);if (a[p*2].rmax + a[p*2+1].lmax >= d) return a[p*2].r-a[p*2].rmax+1;return ask(p*2+1,d);
}int main(void)
{
    freopen("hotel.in","r",stdin);freopen("hotel.out","w",stdout);n = read();m = read();build(1,1,n);while (m --){
    int opt = read();if (opt == 1) {
    int d = read();int ans = ask(1,d);if (a[1].max < d) cnt ++;else Ans[++cnt] = ans,  change(1,ans,ans+d-1,1);}if (opt == 2){
    int x = read(), d = read();change(1,x,x+d-1,2);}}for (int i=1;i<=cnt;++i) printf("%d\n", Ans[i]);return 0;
}