USACO08FEB Hotel G

夏佑 | XiaU
  2022-09-01 2022-09-01 创建   2023-09-15 09:14:57 2023-09-15 09:14:57 更新      2.1k 字  10 分钟  

经典线段树问题。

Prob.

\(n\) 个房间，两种操作：

  1. 1 x：在 \([1,n]\) 中寻找一段长度为 \(x\) 的空房区间。若存在，入住这些房间，并输出最小的左端点。若不存在，输出 \(0\)；
  2. 2 l r：\([l,l+r-1]\) 退房。

Sol.

这道题也算是线段树常规操作了。我们要维护连续的空房区间，想想要维护哪些值？

与分治的思想类似，一段空房区间可以全部在左半部分、全部在右半部分、或者左半部分和右半部分都有一部分。那么我们可以维护三个值：从左端点开始的最长空房区间长度、从右端点开始的最长空房区间长度、以及整个区间的最长空房区间长度。我们把它们分别记为 \(lmax,rmax,maxx\)。

那我们想想线段树的各个模块该如何写。

\(\text{pushup}\)

由于我们要维护三个值，那么上传的时候也要上传三个值。

分情况讨论：

\(lmax\) 如何上传？

显然，当前节点的 \(lmax\) 直接选取左区间的 \(lmax\) 就可以了。但是这里有一种特殊情况：当左区间的 \(lmax\) 等于整段左区间的长度时，\(lmax\) 可以继续延伸至右区间的左端。此时 \(lmax\) 应该为左区间的 \(lmax\) 加上有区间的 \(lmax\)。

1
2
if(t[ls].lmax == (t[ls].r - t[ls].l + 1)) t[k].lmax = t[ls].lmax + t[rs].lmax;
else t[k].lmax = t[ls].lmax;

\(rmax\) 如何上传？

与 \(lmax\) 类似，当右区间的 \(rmax\) 等于整段右区间的长度时，\(rmax\) 可以继续延伸至左区间的右端。否则，选取右区间的 \(rmax\)。

1
2
if(t[rs].rmax == (t[rs].r - t[rs].l + 1)) t[k].rmax = t[rs].rmax + t[ls].rmax;
else t[k].rmax = t[rs].rmax;

\(maxx\) 如何上传？

显然，\(maxx\) 直接从左端点开始的长度、右端点开始的长度、以及左右都有的长度中选取最大值即可。左右都有的长度就是左区间的 \(rmax\) 加上右区间的 \(lmax\)。

1
t[k].maxx = max(max(t[ls].maxx, t[rs].maxx), t[ls].rmax + t[rs].lmax);

那么，我们的 \(\text{pushup}\) 就可以这么写了：

1
2
3
4
5
6
7
8
void pushup(int k)
{
    if(t[ls].lmax == (t[ls].r - t[ls].l + 1)) t[k].lmax = t[ls].lmax + t[rs].lmax;
    else t[k].lmax = t[ls].lmax;
    if(t[rs].rmax == (t[rs].r - t[rs].l + 1)) t[k].rmax = t[rs].rmax + t[ls].rmax;
    else t[k].rmax = t[rs].rmax;
    t[k].maxx = max(max(t[ls].maxx, t[rs].maxx), t[ls].rmax + t[rs].lmax);
}

\(\text{pushdown}\)

当然，区间修改就一定要打懒标记。虽然这道题目的修改不是常规的数值修改，我们仍然要打 \(tag\)。

注意到修改操作有两种：开房和退房。那么我们的 \(tag\) 可以分别用 \(0/1/2\) 表示 无标记/开房/退房。

那么当 \(tag=1\) 时，整段区间都不可用，\(lmax=rmax=maxx=0\)。

当 \(tag=2\) 时，整段区间都可用，\(lmax=rmax=maxx=len\)，\(len\) 为区间长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void pushdown(int k)
{
    if(t[k].tag == 0) return; //无标记返回
    else if(t[k].tag == 1) //开房标记，整段区间不可用
    {
        t[ls].tag = t[rs].tag = 1;
        t[ls].lmax = t[ls].rmax = t[ls].maxx = 0;
        t[rs].lmax = t[rs].rmax = t[rs].maxx = 0;
    }
    else if(t[k].tag == 2) //退房标记，整段区间都可用
    {
        t[ls].tag = t[rs].tag = 2;
        t[ls].lmax = t[ls].rmax = t[ls].maxx = t[ls].r - t[ls].l + 1;
        t[rs].lmax = t[rs].rmax = t[rs].maxx = t[rs].r - t[rs].l + 1;
    }
    t[k].tag = 0; //别忘了清零标记
}

\(\text{build}\)

这个和常规操作没什么不同，只是由于初始全部都是空房，把所有 \(lmax,rmax,maxx\) 赋为当前区间长度就可以了。

\(\text{update}\)

修改操作有两个：开房和退房。但是大体上没什么不同，可以只用一个函数解决。

当是开房操作时，整段区间不可用，\(lmax=rmax=maxx=0\)，打上 \(1\) 标记。

当是退房操作时，整段区间都可用，\(lmax=rmax=maxx=len\)，打上 \(2\) 标记。

函数添加一个参数 \(type\)，\(1/2\) 分别表示 开房/退房 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void update(int k, int l, int r, int type)
{
    if(l <= t[k].l && t[k].r <= r)
    {
        if(type == 1)
        {
            t[k].lmax = t[k].rmax = t[k].maxx = 0;
            t[k].tag = 1;
        }
        else if(type == 2)
        {
            t[k].lmax = t[k].rmax = t[k].maxx = t[k].r - t[k].l + 1;
            t[k].tag = 2;
        }
        return;
    }
    pushdown(k);
    int mid = t[k].l + t[k].r >> 1;
    if(l <= mid) update(ls, l, r, type);
    if(r > mid) update(rs, l, r, type);
    pushup(k);
}

\(\text{query}\)

查询时，要从三部分查询：全部在左区间找、在中间找、全部在右区间找。

这里有一个优先级的问题：由于我们要输出最小的编号，那么应该是左区间→中间→右区间的顺序。

所以，如果左儿子的 \(maxx>=len(len为要查询的长度)\)，那么就从左儿子里找。否则，如果左儿子的 \(rmax\) 加上右儿子的 \(lmax\) 大于等于 \(len\)（也就是跨左右儿子的空房区间），那么直接输出这段的左端点。否则，去右儿子里找。

1
2
3
4
5
6
7
8
int query(int k, int len)
{
    if(t[k].l == t[k].r) return t[k].l;
    pushdown(k);
    if(t[ls].maxx >= len) return query(ls, len); //去左儿子里找
    else if(t[ls].rmax + t[rs].lmax >= len) return t[ls].r - t[ls].rmax + 1; //去中间找，答案就是左儿子 rmax 的左端点，可以用左儿子的右端点 - rmax长度 + 1 表示
    else return query(rs, len); //去右儿子里找
}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5e4 + 7;

#define ls (k << 1)
#define rs (k << 1 | 1)

inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * f;
}

int n, q;

struct Tree
{
    int l, r, tag;
    int lmax, rmax, maxx;
}t[MAXN << 2];

void pushup(int k)
{
    if(t[ls].lmax == (t[ls].r - t[ls].l + 1)) t[k].lmax = t[ls].lmax + t[rs].lmax;
    else t[k].lmax = t[ls].lmax;
    if(t[rs].rmax == (t[rs].r - t[rs].l + 1)) t[k].rmax = t[rs].rmax + t[ls].rmax;
    else t[k].rmax = t[rs].rmax;
    t[k].maxx = max(max(t[ls].maxx, t[rs].maxx), t[ls].rmax + t[rs].lmax);
}

void pushdown(int k)
{
    if(t[k].tag == 0) return;
    else if(t[k].tag == 1)
    {
        t[ls].tag = t[rs].tag = 1;
        t[ls].lmax = t[ls].rmax = t[ls].maxx = 0;
        t[rs].lmax = t[rs].rmax = t[rs].maxx = 0;
    }
    else if(t[k].tag == 2)
    {
        t[ls].tag = t[rs].tag = 2;
        t[ls].lmax = t[ls].rmax = t[ls].maxx = t[ls].r - t[ls].l + 1;
        t[rs].lmax = t[rs].rmax = t[rs].maxx = t[rs].r - t[rs].l + 1;
    }
    t[k].tag = 0;
}

void build(int k, int l, int r)
{
    t[k].tag = 0;
    t[k].l = l, t[k].r = r;
    t[k].maxx = t[k].lmax = t[k].rmax = (r - l + 1);
    if(l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(k);
}

void update(int k, int l, int r, int type)
{
    if(l <= t[k].l && t[k].r <= r)
    {
        if(type == 1)
        {
            t[k].lmax = t[k].rmax = t[k].maxx = 0;
            t[k].tag = 1;
        }
        else if(type == 2)
        {
            t[k].lmax = t[k].rmax = t[k].maxx = t[k].r - t[k].l + 1;
            t[k].tag = 2;
        }
        return;
    }
    pushdown(k);
    int mid = t[k].l + t[k].r >> 1;
    if(l <= mid) update(ls, l, r, type);
    if(r > mid) update(rs, l, r, type);
    pushup(k);
}

int query(int k, int len)
{
    if(t[k].l == t[k].r) return t[k].l;
    pushdown(k);
    if(t[ls].maxx >= len) return query(ls, len);
    else if(t[ls].rmax + t[rs].lmax >= len) return t[ls].r - t[ls].rmax + 1;
    else return query(rs, len);
}

int main()
{
    n = read(), q = read();
    build(1, 1, n);
    while(q--)
    {
        int opt = read();
        if(opt == 1)
        {
            int len = read();
            if(t[1].maxx < len) //如果整段区间都没有大于等于 len 的空房区间，那么输出 0
            {
                printf("0\n");
                continue;
            }
            int ans = query(1, len);
            printf("%d\n", ans);
            update(1, ans, ans + len - 1, 1); //别忘了开上房
        }
        else if(opt == 2)
        {
            int l = read(), r = read();
            update(1, l, l + r - 1, 2); //退房
        }
    }
    return 0;
}

Ext.

讲个笑话，这道题我调了三次的原因；

  1. 没建树 （lmt：我们要有所建树！）；
  2. Shift 没按上 （导致 93 行加号打成了等号）；
  3. 从 \(l\) 开 \(r\) 个房，不是从 \(l\) 开到 \(r\) （所以在 Prob. 里面特意说了是 [l, r-l+1]）。
  • 标题: USACO08FEB Hotel G
  • 作者: 夏佑 | XiaU
  • 创建于 : 2022-09-01 00:00:00
  • 更新于 : 2023-09-15 09:14:57
  • 链接: https://oi.xiau.ren/LGP2894/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
此页目录
USACO08FEB Hotel G
  1. 1. Prob.
  2. 2. Sol.
    1. 2.1. \(\text{pushup}\)
      1. 2.1.1. \(lmax\) 如何上传？
      2. 2.1.2. \(rmax\) 如何上传？
      3. 2.1.3. \(maxx\) 如何上传？
    2. 2.2. \(\text{pushdown}\)
    3. 2.3. \(\text{build}\)
    4. 2.4. \(\text{update}\)
    5. 2.5. \(\text{query}\)
  3. 3. Code
    1. 3.1. Ext.