[SHOI2015] 脑洞治疗仪

GitHub 跳转原题关系图返回列表

在线段树中同时维护区间 1 的数量和最长连续 0，并用左优先递归把目标区间最靠前的若干个 0 填成 1。

OJ: luogu

题目 ID: P4344

难度:提高+/省选-

标签:线段树懒标记区间赋值区间最值模拟

日期: 2026-06-21 03:17

题意

初始有一个长度为 n 的 01 序列，开始时全是 1。

支持三类操作：

把一段区间全部变成 0
把一段区间里的正常脑组织挖出来，拿去填另一段区间里最靠左的脑洞
查询一段区间中最长连续 0 的长度

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int n, m;
int a[MAXN];

int query_best_zero(int l, int r) {
    int best = 0;
    int cur = 0;
    for (int i = l; i <= r; i++) {
        if (a[i] == 0) {
            cur++;
            best = max(best, cur);
        } else {
            cur = 0;
        }
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 这是一个直接模拟：
    // 把区间真的改掉，再线性统计最长连续 0。
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        a[i] = 1;
    }

    while (m--) {
        int op;
        cin >> op;
        if (op == 0) {
            int l, r;
            cin >> l >> r;
            for (int i = l; i <= r; i++) {
                a[i] = 0;
            }
        } else if (op == 1) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;

            int healthy_cnt = 0;
            for (int i = x1; i <= y1; i++) {
                if (a[i] == 1) {
                    healthy_cnt++;
                }
            }
            for (int i = x1; i <= y1; i++) {
                a[i] = 0;
            }
            for (int i = x2; i <= y2 && healthy_cnt > 0; i++) {
                if (a[i] == 0) {
                    a[i] = 1;
                    healthy_cnt--;
                }
            }
        } else {
            int l, r;
            cin >> l >> r;
            cout << query_best_zero(l, r) << '\n';
        }
    }

    return 0;
}

brute.cpp 完全按题意模拟：

统计供体区间里有多少个 1
清空供体区间
从左到右扫描目标区间，把最靠前的 0 填成 1
查询时暴力扫最长连续 0

这个思路容易理解，但大数据下显然太慢。

这题的关键是把所有操作都放进线段树。

线段树每个节点需要维护：

区间里 1 的数量
前缀连续 0
后缀连续 0
最长连续 0

这样：

区间清空就是整段赋值为 0
查询最长脑洞就是查区间 best_zero

操作 1 虽然特殊，但也可以拆开：

先查供体区间里当前有多少个 1
把供体区间整段设为 0
再把目标区间里最靠左的若干个 0 改成 1

第三步用一个左优先递归就能实现：

如果某个完整节点里的 0 数量已经不超过还需填的数量，就整段直接设成 1
否则继续优先递归左儿子，再递归右儿子

这正好对应题意里“尽量填补位置比较靠前的脑洞”。

可以用下面这个小表格理解样例里的第一次治疗：

步骤	区间状态
初始挖洞后	`1 0 1 0 0 0 1 1 1 0`
挖出 `[8,10]` 后拿到的正常组织数	`2`
清空 `[8,10]` 后	`1 0 1 0 0 0 1 0 0 0`
从左到右填补 `[1,4]` 后	`1 1 1 1 0 0 1 0 0 0`

这张表里最重要的是最后一步：目标区间不会把已有的 1 改掉，而是只会把最靠左的两个 0 补上。这正是代码里 fill_leftmost_zero() 的行为。

代码

cpp

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000 + 5;

struct NodeInfo {
    int len;
    int one_cnt;
    int pre_zero;
    int suf_zero;
    int best_zero;
};

int n, m;
int one_cnt[MAXN << 2];
int pre_zero[MAXN << 2];
int suf_zero[MAXN << 2];
int best_zero[MAXN << 2];
int lazy_tag[MAXN << 2];

NodeInfo merge_info(const NodeInfo &left_info, const NodeInfo &right_info) {
    if (left_info.len == 0) {
        return right_info;
    }
    if (right_info.len == 0) {
        return left_info;
    }

    NodeInfo res;
    res.len = left_info.len + right_info.len;
    res.one_cnt = left_info.one_cnt + right_info.one_cnt;

    res.pre_zero = left_info.pre_zero;
    if (left_info.pre_zero == left_info.len) {
        res.pre_zero = left_info.len + right_info.pre_zero;
    }

    res.suf_zero = right_info.suf_zero;
    if (right_info.suf_zero == right_info.len) {
        res.suf_zero = right_info.len + left_info.suf_zero;
    }

    res.best_zero = max(left_info.best_zero, right_info.best_zero);
    res.best_zero = max(res.best_zero, left_info.suf_zero + right_info.pre_zero);
    return res;
}

void apply_set(int u, int l, int r, int val) {
    lazy_tag[u] = val;
    if (val == 0) {
        one_cnt[u] = 0;
        pre_zero[u] = r - l + 1;
        suf_zero[u] = r - l + 1;
        best_zero[u] = r - l + 1;
    } else {
        one_cnt[u] = r - l + 1;
        pre_zero[u] = 0;
        suf_zero[u] = 0;
        best_zero[u] = 0;
    }
}

void push_up(int u, int l, int r) {
    int mid = (l + r) >> 1;
    NodeInfo left_info;
    left_info.len = mid - l + 1;
    left_info.one_cnt = one_cnt[u << 1];
    left_info.pre_zero = pre_zero[u << 1];
    left_info.suf_zero = suf_zero[u << 1];
    left_info.best_zero = best_zero[u << 1];

    NodeInfo right_info;
    right_info.len = r - mid;
    right_info.one_cnt = one_cnt[u << 1 | 1];
    right_info.pre_zero = pre_zero[u << 1 | 1];
    right_info.suf_zero = suf_zero[u << 1 | 1];
    right_info.best_zero = best_zero[u << 1 | 1];

    NodeInfo res = merge_info(left_info, right_info);
    one_cnt[u] = res.one_cnt;
    pre_zero[u] = res.pre_zero;
    suf_zero[u] = res.suf_zero;
    best_zero[u] = res.best_zero;
}

void push_down(int u, int l, int r) {
    if (lazy_tag[u] == -1 || l == r) {
        return;
    }

    int mid = (l + r) >> 1;
    apply_set(u << 1, l, mid, lazy_tag[u]);
    apply_set(u << 1 | 1, mid + 1, r, lazy_tag[u]);
    lazy_tag[u] = -1;
}

void build(int u, int l, int r) {
    lazy_tag[u] = -1;
    if (l == r) {
        // 初始时所有位置都正常工作，也就是全是 1。
        apply_set(u, l, r, 1);
        return;
    }

    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u, l, r);
}

void range_set(int u, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        apply_set(u, l, r, val);
        return;
    }

    push_down(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        range_set(u << 1, l, mid, ql, qr, val);
    }
    if (qr > mid) {
        range_set(u << 1 | 1, mid + 1, r, ql, qr, val);
    }
    push_up(u, l, r);
}

NodeInfo query_info(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        NodeInfo res;
        res.len = r - l + 1;
        res.one_cnt = one_cnt[u];
        res.pre_zero = pre_zero[u];
        res.suf_zero = suf_zero[u];
        res.best_zero = best_zero[u];
        return res;
    }

    push_down(u, l, r);
    int mid = (l + r) >> 1;
    if (qr <= mid) {
        return query_info(u << 1, l, mid, ql, qr);
    }
    if (ql > mid) {
        return query_info(u << 1 | 1, mid + 1, r, ql, qr);
    }

    NodeInfo left_info = query_info(u << 1, l, mid, ql, qr);
    NodeInfo right_info = query_info(u << 1 | 1, mid + 1, r, ql, qr);
    return merge_info(left_info, right_info);
}

void fill_leftmost_zero(int u, int l, int r, int ql, int qr, int &need) {
    if (need == 0 || qr < l || r < ql) {
        return;
    }

    int zero_cnt = (r - l + 1) - one_cnt[u];
    if (zero_cnt == 0) {
        return;
    }

    if (ql <= l && r <= qr && zero_cnt <= need) {
        apply_set(u, l, r, 1);
        need -= zero_cnt;
        return;
    }

    if (l == r) {
        apply_set(u, l, r, 1);
        need--;
        return;
    }

    push_down(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        fill_leftmost_zero(u << 1, l, mid, ql, qr, need);
    }
    if (qr > mid && need > 0) {
        fill_leftmost_zero(u << 1 | 1, mid + 1, r, ql, qr, need);
    }
    push_up(u, l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    build(1, 1, n);

    while (m--) {
        int op;
        cin >> op;

        if (op == 0) {
            int l, r;
            cin >> l >> r;
            range_set(1, 1, n, l, r, 0);
        } else if (op == 1) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;

            NodeInfo source_info = query_info(1, 1, n, x1, y1);
            int healthy_cnt = source_info.one_cnt;

            // 先把供体区间全部挖空，再把这些 1 从左到右填到目标区间的脑洞里。
            range_set(1, 1, n, x1, y1, 0);
            fill_leftmost_zero(1, 1, n, x2, y2, healthy_cnt);
        } else {
            int l, r;
            cin >> l >> r;
            NodeInfo ans = query_info(1, 1, n, l, r);
            cout << ans.best_zero << '\n';
        }
    }

    return 0;
}

复杂度

建树是 $O(n)$ 。

三类操作都可以控制在 $O(log n)$ 量级，因此总复杂度是 $O(m log n)$ ，空间复杂度是 $O(n)$ 。

总结

这题表面上是一个很怪的治疗过程，实际上核心就是两件事：

线段树维护最长连续 0
用左优先递归实现“填最靠前的脑洞”

只要把操作 1 拆成“统计 + 清空 + 左优先填补”，整题就顺了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P4344 [SHOI2015] 脑洞治疗仪

题目描述

曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。

为了简单起见，我们将大脑视作一个 01 序列。 $1$ 代表这个位置的脑组织正常工作， $0$ 代表这是一块脑洞。

cpp

11      0      1      0      0      0      1      1      1      0

脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出，将其中正常工作的脑组织填补在这块脑洞中。（所以脑洞治疗仪是脑洞的治疗仪？）

例如，用上面第 $8$ 号位置到第 $10$ 号位置去修补第 $1$ 号位置到第 $4$ 号位置的脑洞，我们就会得到：

cpp

11      1      1      1      0      0      1      0      0      0

如果再用第 $1$ 号位置到第 $4$ 号位置去修补第 $8$ 号位置到第 $10$ 号位置：

cpp

10      0      0      0      0      0      1      1      1      1

这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。

如果再用第 $7$ 号位置到第 $10$ 号位置去填补第 $1$ 号位置到第 $6$ 号位置：

cpp

11      1      1      1      0      0      0      0      0      0

这是因为如果新脑洞挖出来的脑组织不够多，脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。

假定初始时 SHTSC 并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答 SHTSC 的问题：在大脑某个区间中最大的连续脑洞区域有多大。

输入格式

第一行两个整数 $n,m$ ，表示 SHTSC 的大脑可分为从 $1$ 到 $n$ 编号的 $n$ 个连续区域，有 $m$ 个操作。

以下 $m$ 行每行是下列三种格式之一：

$0\quad l\quad r$ ：SHTSC 挖了一个范围为 $[l, r]$ 的脑洞。
$1\quad l_0\quad r_0\quad l_1\quad r_1$ ：SHTSC 进行了一次脑洞治疗，用从 $l_0$ 到 $r_0$ 的脑组织修补 $l_1$ 到 $r_1$ 的脑洞。
$2\quad l\quad r$ ：SHTSC 询问 $[l, r]$ 区间内最大的脑洞有多大。

上述区间均在 $[1, n]$ 范围内。

输出格式

对于每个询问，输出一行一个整数，表示询问区间内最大连续脑洞区域有多大。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

对于 $20\%$ 的数据， $n, m \leq 100$ ；
对于 $50\%$ 的数据， $n, m \leq 20000$ ；
对于 $100\%$ 的数据， $n, m \leq 200000$ 。

[SHOI2015] 脑洞治疗仪

目录

题意

思路

代码

复杂度

总结

一图流解析