形式化题目

有一条长度为 $N$ 的 0/1 序列，初始全为 0。需要在线处理 $M$ 次操作：

• 入住：给定 $D$，找出第一个长度至少为 $D$ 的全 0 连续段，返回它的左端点（房间号从 1 开始）， 并把该段（前 $D$ 个位置）全部置为 1；若不存在这样的段，返回 $0$ 且不改变序列。
• 退房：给定 $X, D$，把区间 $[X, X + D - 1]$ 整段置为 0。

「房间号尽可能小」不是额外的贪心条件，它就是查询规则：返回所有合法连续段中最靠左的那个起点。

$N \leqslant 50000$，$M < 50000$。这个规模要求每次操作 $O(\log N)$ 量级。

暴力解法

思路

直接用一个布尔数组 occ[1..N] 模拟：

• 退房逐个清空；
• 入住从 1 开始扫，用 run 记录当前位置结尾的连续空房长度，一旦 run == D 就确定起点 i - D + 1。

1
2
3
4
5
6
7
8
9
10入住 (1 D):
    run = 0
    for i in 1..N:
        run = run + 1 if occ[i] 是空 else 0
        if run == D:
            把 [i-D+1, i] 置为已住 ; 输出 i-D+1 ; break
    扫完仍未找到: 输出 0

退房 (2 X D):
    for i in X..X+D-1: occ[i] = 空

正确性显然：run 就是「以 $i$ 结尾的最长空段长度」，第一次达到 $D$ 的位置对应最靠左的合法起点。

代码

按任务要求本题不提供 brute.cpp：暴力只是「维护 0/1 数组 + 线性扫描」， 思想上没有额外教学价值，瓶颈本身已经说明问题。验证改用真实测试数据。

复杂度

• 时间：单次入住 $O(N)$，单次退房 $O(D)$，最坏 $O(NM) = 2.5 \times 10^9$ 次访问。
• 空间：$O(N)$。

瓶颈

慢的不是「改房间」——退房最多改 $N$ 间，均摊可接受；真正的瓶颈是每次入住都要从头重扫整排房间。

问题的核心是「第一个长度至少为 $D$ 的全 0 连续段在哪」。注意它不能用「区间里有多少个空房」 代替：一段区间里空房再多，也可能被已入住的房间切成碎片，凑不出连续 $D$ 间。 所以前缀和、差分、树状数组都答不了这个问题——它们只统计个数，不掌握「连续」这个信息。

要提速，必须让每一段区间自己携带「连续空房」的结构信息，并且这些信息要能合并。

正解

关键观察

观察 1：连续空段可以用四个量概括。 对任意区间 $[l, r]$，只要记录

就能把它与相邻区间拼起来。$\text{pre}$ 与 $\text{suf}$ 的「贴边」约束是关键：只有贴着边， 两块拼起来才仍然是连续的一段。

观察 2：合并式只用这四个量。 设左段 $L$、右段 $R$，

以 $\text{pre}$ 为例：贴着左端的空段要么没越过中缝（最长是 $L.\text{pre}$）， 要么整段吃掉 $L$；而能吃下 $L$ 的前提是 $L$ 整段都空，即 $L.\text{pre} = L.\text{len}$。 $\text{best}$ 的第三项 $L.\text{suf} + R.\text{pre}$ 正是「跨越中缝」的最优候选。 这三个量互相封闭：合并结果仍然只需要 $\text{pre}/\text{suf}/\text{best}$， 与区间长度无关（$\text{len}$ 只需单独相加），所以这个运算可以任意嵌套。

观察 3：最靠左的可行起点可以在树上贪心求得。 有了 $\text{best}$，查询 $D$ 只需一条下降路径：

1. 左孩子的 $\text{best} \geqslant D$ ⇒ 左孩子内部就有，答案一定在左边；
2. 否则 $\text{suf}[\text{左}] + \text{pre}[\text{右}] \geqslant D$ ⇒ 合法段正好贴着中缝跨越， 起点是 $\text{mid} - \text{suf}[\text{左}] + 1$，可直接返回；
3. 否则答案只可能在右孩子。

三步的优先级就是「尽可能小」的实现，因为左孩子覆盖的房间号全都小于右孩子。

下面用 8 个房间、房间 $3, 4$ 已入住的状态展示这几个量（数字由 problem-analysis-workspace/viz_render.py 从 main.py 打印，与代码一致）：

1
2
3
4
5
6
7
8
9房间:    1 2 3 4 5 6 7 8
状态:    . . # # . . . .
                    |
                    v
节点1 [1,8]  len=8  pre=2  suf=4  best=4
├─ 节点2 [1,4]  len=4  pre=2  suf=0  best=2
│  ├─ [1,2] len=2 pre=2 suf=2 best=2
│  └─ [3,4] len=2 pre=0 suf=0 best=0     <- 住满: 三个量全 0
└─ 节点3 [5,8]  len=4  pre=4  suf=4  best=4

根节点的 best = max(2, 4, 0 + 4) = 4：左孩子的 best = 2、右孩子的 best = 4、 跨中缝的 suf[2] + pre[3] = 0 + 4 = 4，其中右孩子那 4 间就是房间 5–8。 节点 [1,4] 的 pre = 2 而 suf = 0（右端房间 4 已住，贴右后缀为空）， 两个贴边量可以完全不同，这正是「贴边」的含义。

换一个状态 ##...#..（房间 1、2、6 已住），它同时能触到三个分支：

根节点的 $\text{best} = \max(2, 2, 2 + 1) = 3$ 由跨中缝那一项胜出，对应空房 3、4、5。于是：查询 $D = 2$ 时 $\text{best}[1,4] = 2 \geqslant 2$，走第 1 个分支 （继续往左），最终返回 3；查询 $D = 3$ 时 $\text{best}[1,4] = 2 < 3$ 但 $\text{suf}[1,4] + \text{pre}[5,8] = 2 + 1 = 3 \geqslant 3$，走第 2 个分支， 直接返回 $4 - 2 + 1 = 3$；查询 $D = 4$ 时两个候选都不够，返回 0。 同一个 $\text{best}[1,8] = 3$ 在不同 $D$ 下被不同的分支用掉，这正是「$\text{best}$ 交给树上现算」而不是「预先存下每个 $D$ 的答案」的原因。

观察 4：$\text{len}$ 必须是实际房间数。 线段树需要在 $[1, M]$ 上递归，其中 $M$ 是 $\geqslant N$ 的最小 2 的幂；$M - N$ 个补位叶代表不存在的房间，它们的 $\text{len} = 0$。 否则右端一串假房间会被当成真实空房，当 $D$ 较大时可能返回一个 $> N$ 的起点 （例如 $N = 5$ 时房间 2、3 住人，查询 $D = 2$ 必须给 4，而不能越过 5）。

思路

线段树节点与懒标记

用带懒标记的线段树维护上述四个量。区间赋值天然适合懒标记：整段刷成同一颜色时， 要么整段空（$\text{pre} = \text{suf} = \text{best} = \text{len}$），要么整段满（三者均为 0）， 可以 $O(1)$ 算出：

1
2
3
4apply(node, color):
    empty = 0 if color == 已住 else len[node]
    pre[node] = suf[node] = best[node] = empty
    lazy[node] = color

push 把标记下传给孩子并清空自己的标记；modify 在完整覆盖时直接 apply 并返回， 否则 push 后递归、最后 pull 回来。

查询：先 push 再比较

1
2
3
4
5
6
7
8query(node, l, r, D):
    if best[node] < D:  return 0            # 这一段连 D 间空房都没有
    if l == r:          return l            # 走到叶子, best >= D 只能是 D == 1
    push(node)                              # 先下传标记, 孩子的量才是最新的
    mid = (l + r) // 2
    if best[左] >= D:              return query(左, l, mid, D)
    if suf[左] + pre[右] >= D:     return mid - suf[左] + 1
    return query(右, mid + 1, r, D)

两个容易写错的点：

• 比较之前必须 push，否则孩子身上可能还挂着父节点的懒标记，读到的是过期数据；
• 第 2 步的返回值是 $\text{mid} - \text{suf}[\text{左}] + 1$，不是 $\text{mid} + 1$： 跨中缝的空段由「$L$ 的贴右后缀 + $R$ 的贴左前缀」构成，起点要往左回退 $\text{suf}[\text{左}]$ 间。 它不需要进入孩子就能算出来，这也是查询只走一条路径、不拆区间的原因。

用样例推一遍

$N = 10$，业务序列为 $1\,3,\ 1\,3,\ 1\,3,\ 1\,3,\ 2\,5\,5,\ 1\,6$：

（# 表示已入住，. 表示空房。）

第 4 步是关键：只剩第 10 间空房，$\text{best}[1] = 1 < 3$，query 直接返回 0， 且不调用 modify，所以第 5 步退房清空 5–9 号房间后，房间 5–10 恰好连成 6 间， 第 6 步的 1 6 才能在起点 5 入住成功。若查询失败时仍然改动了状态， 或者把补位叶的 $\text{len}$ 记成 1（$N = 10$ 时 $M = 16$，有 6 个补位叶）， 这里的输出就会出错。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// Hotel：线段树维护连续空房，支持「最靠左的 d 间连续空房」与区间清空。
#include <cstdio>

typedef long long ll;

const ll MAXN = 100005;
const ll NONE = -1;  // 延迟标记：-1 无标记，0 整段清空，1 整段入住
const ll OCCUPY = 1, CLEAR = 0;

ll length[MAXN * 4]; // 每个节点覆盖的房间数
ll pre[MAXN * 4];    // 该段从左端起的最长连续空房数
ll suf[MAXN * 4];    // 该段从右端起的最长连续空房数
ll best[MAXN * 4];   // 该段内部的最长连续空房数
ll lazy[MAXN * 4];   // 延迟标记

// 建树：叶子记区间长度（超出 n 的补 0），初始全部空房
ll prepare(ll n) {
    ll M = 1; // 叶子数，同时就是房间坐标的上界
    while (M < n) M <<= 1;
    ll size = M << 1;
    for (ll i = 0; i < size; i++) {
        length[i] = 0;
        pre[i] = suf[i] = best[i] = 0;
        lazy[i] = NONE;
    }
    for (ll i = M; i < size; i++) {
        if (1 <= i - M + 1 && i - M + 1 <= n) length[i] = 1;
        // 叶子：三个统计量都与区间长度相同（length 只取 0 / 1）
        pre[i] = suf[i] = best[i] = length[i];
    }
    for (ll i = M - 1; i >= 1; i--) { // 自底向上累加出每个节点的区间长度
        length[i] = length[i << 1] + length[i << 1 | 1];
        pre[i] = suf[i] = best[i] = length[i];
    }
    return M;
}

// 把 node 整段刷成 color：入住则空房归零，清空则整段都是空房
void apply(ll node, ll color) {
    ll empty = (color == OCCUPY) ? 0 : length[node];
    pre[node] = suf[node] = best[node] = empty;
    lazy[node] = color;
}

// 把 node 的延迟标记下传给孩子，并清掉自己的标记
void push(ll node) {
    ll tag = lazy[node];
    if (tag != NONE) {
        apply(node << 1, tag);
        apply(node << 1 | 1, tag);
        lazy[node] = NONE;
    }
}

// 由两个孩子重算 node 的三个空房统计量
void pull(ll node) {
    ll left = node << 1, right = node << 1 | 1;
    pre[node] = pre[left] + (pre[left] == length[left] ? pre[right] : 0);
    suf[node] = suf[right] + (suf[right] == length[right] ? suf[left] : 0);
    ll b = best[left] > best[right] ? best[left] : best[right];
    ll cross = suf[left] + pre[right];
    best[node] = b > cross ? b : cross;
}

// 把房间区间 [ql, qr] 整段刷成 color
void modify(ll node, ll l, ll r, ll ql, ll qr, ll color) {
    if (ql <= l && r <= qr) { // 当前段被完全覆盖，整段打标记
        apply(node, color);
        return;
    }
    push(node);
    ll mid = (l + r) >> 1;
    if (ql <= mid) modify(node << 1, l, mid, ql, qr, color);
    if (qr > mid) modify(node << 1 | 1, mid + 1, r, ql, qr, color);
    pull(node);
}

// 找最靠左的、能装下 d 个连续空房的起点房间号；装不下返回 0
ll query(ll node, ll l, ll r, ll d) {
    if (best[node] < d) return 0;
    if (l == r) return l; // 走到叶子说明 d 必为 1
    push(node);
    ll mid = (l + r) >> 1;
    ll left = node << 1, right = node << 1 | 1;
    if (best[left] >= d) return query(left, l, mid, d);      // 优先最左
    if (suf[left] + pre[right] >= d) return mid - suf[left] + 1; // 跨在交界处
    return query(right, mid + 1, r, d);
}

int main() {
    ll n, m;
    if (scanf("%lld %lld", &n, &m) != 2) return 0; // 空输入安全返回
    ll M = prepare(n);

    ll outs = 0; // 真正输出过的询问个数
    for (ll q = 0; q < m; q++) {
        ll op;
        scanf("%lld", &op);
        if (op == 1) {
            ll d;
            scanf("%lld", &d);
            ll start = query(1, 1, M, d);
            printf("%lld\n", start);
            outs++;
            if (start) { // 找到才真的入住
                modify(1, 1, M, start, start + d - 1, OCCUPY);
            }
        } else {
            ll x, d;
            scanf("%lld %lld", &x, &d);
            modify(1, 1, M, x, x + d - 1, CLEAR);
        }
    }
    if (outs == 0) printf("\n"); // 与 Python 的 print('\n'.join([])) 一致
    return 0;
}

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 18:30
# update_at: 2026-10-01 18:30

import sys

NONE = -1      # 延迟标记：-1 无标记，0 整段清空，1 整段入住
OCCUPY, CLEAR = 1, 0  # 与延迟标记同义的业务含义，避免在调用点裸写 1 / 0

length: list[int] = []  # 每个节点覆盖的房间数
pre: list[int] = []     # 该段从左端起的最长连续空房数
suf: list[int] = []     # 该段从右端起的最长连续空房数
best: list[int] = []    # 该段内部的最长连续空房数
lazy: list[int] = []    # 延迟标记，含义见 NONE


def prepare(n: int) -> int:
    """建树：叶子记区间长度（超出 n 的补 0），初始全部空房，标记清空；返回叶子数 M。

    线段树按 [1, M] 的坐标递归，M 是大于等于 n 的最小 2 的幂；补出来的 M - n
    个假房间长度为 0，永远不可能被选中，却让左右孩子的分界点保持整齐。
    """
    global length, pre, suf, best, lazy
    M = 1 << (n - 1).bit_length()        # 叶子数，同时就是房间坐标的上界
    size = M << 1
    length = [1 if 1 <= i - M + 1 <= n else 0 for i in range(size)]
    for i in range(M - 1, 0, -1):        # 自底向上累加出每个节点的区间长度
        length[i] = length[i << 1] + length[i << 1 | 1]
    pre, suf, best = length.copy(), length.copy(), length.copy()
    lazy = [NONE] * size
    return M


def apply(node: int, color: int) -> None:
    """把 node 整段刷成 color：入住则空房归零，清空则整段都是空房。"""
    empty = 0 if color == OCCUPY else length[node]
    pre[node] = suf[node] = best[node] = empty
    lazy[node] = color


def push(node: int) -> None:
    """把 node 的延迟标记下传给孩子，并清掉自己的标记。"""
    tag = lazy[node]
    if tag != NONE:
        apply(node << 1, tag)
        apply(node << 1 | 1, tag)
        lazy[node] = NONE


def pull(node: int) -> None:
    """由两个孩子重算 node 的三个空房统计量。"""
    left, right = node << 1, node << 1 | 1
    # 左孩子整段全空时，前缀才能越过它继续接上右孩子的前缀
    pre[node] = pre[left] + (pre[right] if pre[left] == length[left] else 0)
    suf[node] = suf[right] + (suf[left] if suf[right] == length[right] else 0)
    best[node] = max(best[left], best[right], suf[left] + pre[right])


def modify(node: int, l: int, r: int, ql: int, qr: int, color: int) -> None:
    """把房间区间 [ql, qr] 整段刷成 color。"""
    if ql <= l and r <= qr:              # 当前段被完全覆盖，整段打标记
        apply(node, color)
        return
    push(node)
    mid = (l + r) >> 1
    if ql <= mid:
        modify(node << 1, l, mid, ql, qr, color)
    if qr > mid:
        modify(node << 1 | 1, mid + 1, r, ql, qr, color)
    pull(node)


def query(node: int, l: int, r: int, d: int) -> int:
    """找最靠左的、能装下 d 个连续空房的起点房间号；装不下返回 0。"""
    if best[node] < d:                   # 本段最长空房都不够，整段无解
        return 0
    if l == r:
        return l                         # 走到叶子说明 d 必为 1，就是这一间
    push(node)
    mid = (l + r) >> 1
    left, right = node << 1, node << 1 | 1
    if best[left] >= d:                  # 优先最左：左孩子内部就能装下
        return query(left, l, mid, d)
    if suf[left] + pre[right] >= d:      # 其次：正好跨在左右孩子交界处
        return mid - suf[left] + 1
    return query(right, mid + 1, r, d)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    M = prepare(n)

    out: list[str] = []
    for _ in range(m):
        op = next(data)
        if op == 1:
            d = next(data)
            start = query(1, 1, M, d)
            out.append(str(start))
            if start:                    # 找到才真的入住，找不到就只是报 0
                modify(1, 1, M, start, start + d - 1, OCCUPY)
        else:
            x, d = next(data), next(data)
            modify(1, 1, M, x, x + d - 1, CLEAR)

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

实现说明：

• NONE = -1 是「无标记」哨兵。0 和 1 已经是真实颜色，不能拿它们当「无」； 因此 lazy 初始化为 $-1$ 而不是 0。
• OCCUPY、CLEAR 只是给两个颜色起名，避免在调用点裸写 1 / 0。
• 五个数组是模块级全局量，prepare 用 global 一次性重新绑定，避免把大数组 当参数在递归里反复传递。
• query 与 modify 里的判断都先取局部变量 left、right、mid 再比较， 避免在 if 条件里塞复合表达式。

复杂度

• 建树 $O(N)$：叶子层规模 $M < 2N$，两次线性扫描。
• 单次业务 $O(\log N)$：modify 是标准区间赋值；query 沿唯一路径下降到叶子， 每个节点 $O(1)$。
• 总计 $O(N + M\log N)$，空间 $O(N)$，与标准 C++ 正解同阶。 $N, M = 5 \times 10^4$ 时约 $1.6 \times 10^6$ 次节点访问，实测最大测试点 0.39 s / 26 MB， 在 1000 ms / 128 MB 限制内。

总结

• 「第一个长度 $\geqslant D$ 的全 0 连续段」不能靠区间求和回答，因为空房个数与 连续空房长度是两件事；必须让区间携带 $\text{pre}/\text{suf}/\text{best}$ 这类 连续段信息。
• 贴左、贴右两个量是让信息可合并的关键：只有贴着边，两段拼起来才仍然连续； 于是 $\text{best}$ 的第三种情况可以显式写成 $L.\text{suf} + R.\text{pre}$， 三个量互相封闭、可结合。
• 有了可合并的 $\text{best}$，「尽可能小的房间号」变成树上一次优先级为 「左 → 中缝 → 右」的下降；中缝那一步可以直接算出起点，不必进入孩子。
• 补位叶的 $\text{len}$ 必须为 0，且查询失败时不能真的入住——这两点都源于 「$N$ 不一定等于 2 的幂」和「业务失败不改变状态」。

图示解析

从题面到答案的完整路线：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20   题目要求: 最靠左的长度 >= D 的连续空房
                    |
                    v
   区间需要携带三个量:  pre(贴左) / suf(贴右) / best(段内)
        + len = 实际房间数 (补位叶 len = 0)
                    |
                    v
   合并式:  pre  = L.pre + (R.pre if L.pre == L.len else 0)
            suf  = R.suf + (L.suf if R.suf == R.len else 0)
            best = max(L.best, R.best, L.suf + R.pre)
                    |
                    v
   线段树 + 懒标记 (区间染色: 入住刷 1 / 退房刷 0)
                    |
        +-----------+-----------+
        v                       v
   修改: modify           查询: query 沿唯一路径下降
        整段覆盖就 apply         best[左] >= D      -> 走左
        否则 push 后递归         suf[左]+pre[右] >= D -> mid-suf[左]+1
        回来 pull                否则                -> 走右

图中第一层是题目要求的目标；第二层是全题唯一的建模决定——一个区间必须携带哪几个 量才能和邻居拼起来，len 之所以在里面，是因为「整段全空」不能靠 pre 自己判断； 第三层是三个合并式，best 的第三项 $L.\text{suf} + R.\text{pre}$ 就是跨越中缝的候选； 第四层把合并式交给线段树；最下面一层是两条操作路径。查询那一列的三个分支按上到下的 顺序排列，优先级就是「房间号尽可能小」。