企业官网建设流程全解析

1. 这道题到底在考什么

第一次看到“脑洞治疗仪”这个标题，很多人会以为是什么医疗设备或者科幻设定，实际上它是一道非常经典的区间操作类数据结构题。题目的核心场景是这样的：有一个长度为 n 的 01 序列，初始时全部为 1，接下来有三种操作——把某段区间全部清零、把某段区间内所有的 1 填充到另一段区间里（优先填左边的空位）、查询某段区间内最长的连续 0 的长度。就是这三种操作来回组合，考察的是对线段树区间合并的深度理解。

我之所以想专门写一篇关于这道题的完整拆解，是因为它几乎涵盖了区间合并类问题的所有关键技巧：区间赋值、区间查询、区间合并、以及一个非常容易写错的“搬运”操作。很多人在学线段树的时候，做区间求和、区间最值都觉得挺顺，但一到区间合并就开始犯迷糊，尤其是涉及到“最长连续满足条件的子段”这种查询，pushup 和 query 的写法跟普通线段树完全不一样。这道题就是一个绝佳的练兵场。

这篇文章适合已经掌握了线段树基本操作、想进一步提升区间合并能力的读者。如果你连线段树的基本 build、pushdown、update 都还没写过，建议先去把基础的区间加、区间求和写熟再来。整篇文章我会从设计思路、核心细节、完整实现、常见错误四个维度展开，把我踩过的坑和总结的技巧都摊开来讲。

2. 整体设计思路与方案选型

2.1 为什么选线段树而不是分块

拿到这道题，第一反应应该是：区间赋值、区间查询、区间合并，这三个需求叠加在一起，线段树是最自然的选择。有人可能会想用分块来做，毕竟分块在区间赋值上也有天然优势（整块打标记），但问题在于查询“最长连续 0”这个操作，分块合并的时候需要维护每块的左端连续 0 长度、右端连续 0 长度、内部最长连续 0 长度，块与块之间的合并逻辑跟线段树节点合并几乎一样复杂，但查询时还需要逐块扫描，复杂度是 O(块数 + 块大小)，调参不好的话很容易被卡。

线段树在这个问题上的优势非常明显：每次操作都是 O(log n)，三种操作可以共用同一套底层结构，代码复用率高。而且区间赋值这个操作在线段树上就是一个标准的 lazy 标记，写起来很顺手。

2.2 每个节点需要维护哪些信息

这是区间合并类问题的核心。对于“最长连续 0”这个查询，一个节点仅仅记录一个“最长连续 0 的长度”是不够的，因为合并两个子区间的时候，跨越中点的连续 0 段可能比左右子区间各自的最长连续 0 段都长。所以每个节点至少需要维护三个值：

• pre：从区间左端点开始，连续 0 的最大长度
• suf：从区间右端点开始，连续 0 的最大长度
• ans：区间内最长连续 0 的长度

除此之外，为了支持区间赋值操作，还需要一个 lazy 标记，表示这个区间被整体赋成了 0 还是 1。我一般用 -1 表示没有标记，0 表示赋为 0，1 表示赋为 1。

另外，为了在 pushup 的时候判断左右子区间是否“全 0”或“全 1”，还需要记录区间长度 len。其实 len 可以在递归过程中传参，但存在节点里更方便。

2.3 合并逻辑的推导

pushup 的合并逻辑是这道题的第一个关键点。假设左儿子为 L，右儿子为 R：

• 当前节点的 pre：如果 L 的 pre 等于 L 的长度（即左儿子全是 0），那么当前 pre = L.len + R.pre；否则当前 pre = L.pre。
• 当前节点的 suf：如果 R 的 suf 等于 R 的长度（即右儿子全是 0），那么当前 suf = R.len + L.suf；否则当前 suf = R.suf。
• 当前节点的 ans：取三者最大值——L.ans、R.ans、L.suf + R.pre。

这个逻辑看起来简单，但写的时候很容易在“全 0 判断”上出错。注意，判断条件是 pre == len 还是 pre == 区间长度，这两个在叶子节点上是一样的，但在非叶子节点上必须用区间长度。我建议直接把 len 存在节点结构体里，避免传参遗漏。

2.4 操作三的“搬运”逻辑拆解

这道题最让人头疼的是操作三：把一段区间 [l0, r0] 内所有的 1 取出来，然后填充到另一段区间 [l1, r1] 里，优先填左边的空位。这个操作实际上可以拆成三步：

1. 统计 [l0, r0] 内 1 的个数，记为 cnt。
2. 把 [l0, r0] 全部赋为 0。
3. 在 [l1, r1] 内从左到右找 cnt 个 0，把它们变成 1。

第一步和第二步都很直接，区间查询加区间赋值就行。第三步是难点，需要在线段树上实现一个“从左到右填充 k 个 0”的操作。这个操作不能简单地用区间赋值完成，因为填充的位置取决于当前哪些位置是 0。

我的做法是写一个专门的 fill 函数，递归地在线段树上找 0 并填充。具体来说，如果当前区间已经被完全覆盖且区间内 0 的个数不超过剩余需要填充的数量，就直接把这个区间整体赋为 1，并返回填充了多少个。否则递归左右儿子，优先递归左儿子。这个函数的复杂度是 O(log n) 均摊的，因为每次填充要么填满一个区间直接返回，要么递归到叶子，总的递归次数不会太多。

3. 核心细节与实现要点

3.1 节点结构体的设计

结构体设计直接决定了后续代码的简洁程度。我的习惯是：

struct Node { int pre, suf, ans; int len; int lazy; // -1 无标记, 0 赋0, 1 赋1 };

这里 len 存在节点里，虽然多了一点空间，但省去了递归传参的麻烦。lazy 初始化为 -1。pre、suf、ans 在 build 的时候全部初始化为 len，因为初始序列全是 1，连续 0 的长度为 0。等等，这里要注意：初始全是 1，所以连续 0 的长度应该是 0，pre、suf、ans 都应该是 0。我见过有人在这里搞反了，把初始值设成 len，结果查询全错。

3.2 区间赋值的 lazy 传播

区间赋值操作的 pushdown 逻辑需要特别小心。当把一个区间赋为 0 时：

• pre = suf = ans = len
• lazy = 0

当把一个区间赋为 1 时：

• pre = suf = ans = 0
• lazy = 1

pushdown 的时候，如果当前节点有 lazy 标记，就把标记下传给左右儿子，然后清除自己的标记。这里有一个易错点：下传标记后，当前节点的 pre、suf、ans 不需要重新计算，因为它们已经被赋值操作直接设置过了。只有 pushup 的时候才需要重新合并。

3.3 查询最长连续 0 的返回值设计

普通的区间查询返回一个数值就行了，但“最长连续 0”的查询不能只返回一个 ans，因为合并两个查询结果的时候需要用到 pre 和 suf。所以查询函数应该返回一个 Node 结构体，表示查询区间的信息。

这里有一个非常容易踩的坑：当查询区间跨越当前节点的中点时，需要把左右两次查询的结果合并。合并的时候不能简单地调用 pushup，因为 pushup 是针对线段树节点设计的，而查询返回的 Node 不一定对应一个完整的线段树节点。所以需要单独写一个 merge 函数，专门用于合并两个查询结果。

merge 函数的逻辑跟 pushup 几乎一样，但要注意 len 的处理：合并后的 len 等于两个 Node 的 len 之和。另外，如果其中一个 Node 是空区间（比如查询区间只落在左半边），需要特殊处理。我的做法是查询函数返回一个 valid 标志，或者用一个特殊值表示空区间。

3.4 fill 函数的实现细节

fill 函数的目标是在区间 [ql, qr] 内从左到右填充 k 个 0。函数签名大概是这样的：

int fill(int p, int l, int r, int ql, int qr, int k);

返回值是实际填充的数量。如果 k 为 0，直接返回 0。如果当前区间被 [ql, qr] 完全覆盖，且区间内 0 的个数不超过 k，那么直接把这个区间赋为 1，返回区间内 0 的个数。否则 pushdown，递归左右儿子，优先递归左儿子。

这里的关键是“区间内 0 的个数”怎么快速得到。可以在 Node 里再维护一个 cnt0，表示区间内 0 的个数。但这样会让 pushup 多维护一个值。另一种做法是用 len - cnt1 来得到 cnt0，但 cnt1 也需要维护。我选择直接维护 cnt0，因为它在 fill 函数里用得很频繁。

维护 cnt0 之后，pushup 里 cnt0 = L.cnt0 + R.cnt0，区间赋值时 cnt0 直接设为 len 或 0。这样 fill 函数就能在 O(1) 时间内判断当前区间是否可以被整体填充。

3.5 操作三的完整流程

把操作三拆解成代码：

// 第一步：统计 [l0, r0] 内 1 的个数 int cnt1 = query1(1, 1, n, l0, r0); // 第二步：把 [l0, r0] 全部赋为 0 update(1, 1, n, l0, r0, 0); // 第三步：在 [l1, r1] 内填充 cnt1 个 1 fill(1, 1, n, l1, r1, cnt1);

注意，如果 cnt1 为 0，第三步可以跳过。另外，如果 l0 > r0 或者 l1 > r1，需要特判。题目保证输入合法，但保险起见还是加上判断。

4. 完整实现与关键代码解析

4.1 建树与 pushup

void pushup(int p) { Node &u = tree[p], &L = tree[p<<1], &R = tree[p<<1|1]; u.cnt0 = L.cnt0 + R.cnt0; u.pre = (L.pre == L.len) ? L.len + R.pre : L.pre; u.suf = (R.suf == R.len) ? R.len + L.suf : R.suf; u.ans = max(max(L.ans, R.ans), L.suf + R.pre); }

建树的时候，初始全是 1，所以 cnt0 = 0，pre = suf = ans = 0，lazy = -1。叶子节点的 len = 1。

4.2 区间赋值与 pushdown

void pushdown(int p) { if (tree[p].lazy != -1) { int v = tree[p].lazy; for (int i = 0; i < 2; i++) { int c = p<<1|i; tree[c].lazy = v; if (v == 0) { tree[c].pre = tree[c].suf = tree[c].ans = tree[c].len; tree[c].cnt0 = tree[c].len; } else { tree[c].pre = tree[c].suf = tree[c].ans = 0; tree[c].cnt0 = 0; } } tree[p].lazy = -1; } }

这里有一个细节：pushdown 的时候不需要判断子节点是否存在，因为线段树的递归保证了只有非叶子节点才会调用 pushdown。

4.3 查询最长连续 0

Node query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[p]; pushdown(p); int mid = (l + r) >> 1; if (qr <= mid) return query(p<<1, l, mid, ql, qr); if (ql > mid) return query(p<<1|1, mid+1, r, ql, qr); Node L = query(p<<1, l, mid, ql, qr); Node R = query(p<<1|1, mid+1, r, ql, qr); return merge(L, R); }

merge 函数的实现：

Node merge(Node L, Node R) { Node u; u.len = L.len + R.len; u.cnt0 = L.cnt0 + R.cnt0; u.pre = (L.pre == L.len) ? L.len + R.pre : L.pre; u.suf = (R.suf == R.len) ? R.len + L.suf : R.suf; u.ans = max(max(L.ans, R.ans), L.suf + R.pre); u.lazy = -1; return u; }

注意，merge 返回的 Node 的 lazy 应该设为 -1，因为它只是一个临时结果，不代表线段树上的真实节点。

4.4 fill 函数的完整实现

int fill(int p, int l, int r, int ql, int qr, int k) { if (k == 0) return 0; if (ql <= l && r <= qr) { if (tree[p].cnt0 <= k) { int filled = tree[p].cnt0; tree[p].lazy = 1; tree[p].pre = tree[p].suf = tree[p].ans = 0; tree[p].cnt0 = 0; return filled; } } if (l == r) return 0; pushdown(p); int mid = (l + r) >> 1; int filled = 0; if (ql <= mid) filled += fill(p<<1, l, mid, ql, qr, k - filled); if (filled < k && qr > mid) filled += fill(p<<1|1, mid+1, r, ql, qr, k - filled); pushup(p); return filled; }

这个函数有几个关键点：第一，当区间被完全覆盖且 cnt0 <= k 时，直接整体填充并返回；第二，递归时优先左儿子；第三，每次递归后要 pushup 更新当前节点。

4.5 主函数的操作分发

int main() { scanf("%d%d", &n, &m); build(1, 1, n); while (m--) { int op, l, r; scanf("%d%d%d", &op, &l, &r); if (op == 0) { update(1, 1, n, l, r, 0); } else if (op == 1) { int l0, r0, l1, r1; scanf("%d%d%d%d", &l0, &r0, &l1, &r1); int cnt1 = query1(1, 1, n, l, r); update(1, 1, n, l, r, 0); fill(1, 1, n, l0, r0, cnt1); } else { Node res = query(1, 1, n, l, r); printf("%d\n", res.ans); } } return 0; }

注意操作 1 的输入格式：题目给的是 l0, r0, l1, r1，其中 l 和 r 是治疗区间，l0 和 r0 是填充目标区间。这里容易搞混，建议在代码里用清晰的变量名。

5. 常见问题与排查技巧实录

5.1 查询结果合并时 pre 和 suf 计算错误

这是最常见的错误。很多人在 merge 函数里写：

u.pre = L.pre + R.pre; // 错误！

正确的写法必须判断 L 是否全 0。如果 L 不全 0，那么 u.pre 就是 L.pre，不能加上 R.pre。这个错误在查询区间恰好跨越中点时才会暴露，平时测试小数据可能看不出来。

排查方法：构造一个查询区间，使得左半部分有 0 有 1，右半部分开头是 0，然后看返回的 pre 是否正确。

5.2 fill 函数死循环或填充数量不对

fill 函数最容易出的问题是递归边界处理不当。比如，当 ql > mid 时不应该递归左儿子，但有些人忘了判断，导致递归到无关区间。另一个问题是 k - filled 的计算，如果 filled 已经等于 k，就不应该继续递归。

排查方法：在 fill 函数里加临时打印，观察每次递归的区间和 k 值。或者用一个小数据手动模拟。

5.3 区间赋值后 lazy 标记未正确下传

这个问题通常表现为：先执行一次区间赋值，再执行查询，结果查询到了旧数据。原因可能是 pushdown 里忘了更新子节点的 cnt0，或者忘了清除当前节点的 lazy。

排查方法：每次 pushdown 后，检查子节点的 pre、suf、ans、cnt0 是否与 lazy 值一致。

5.4 操作三中 cnt1 统计错误

统计 [l0, r0] 内 1 的个数，可以用区间长度减去 cnt0。但要注意，如果查询函数返回的 Node 的 len 不等于区间长度，就会出错。所以 query1 函数应该返回一个准确的 cnt1，而不是依赖 Node 的 len。

我的做法是单独写一个 query1 函数，直接返回区间内 1 的个数：

int query1(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[p].len - tree[p].cnt0; pushdown(p); int mid = (l + r) >> 1; int res = 0; if (ql <= mid) res += query1(p<<1, l, mid, ql, qr); if (qr > mid) res += query1(p<<1|1, mid+1, r, ql, qr); return res; }

5.5 常见问题速查表

5.6 几个实用的调试技巧

第一，写一个暴力程序，随机生成小数据，对拍。这道题的暴力很好写，直接模拟数组操作就行。对拍能发现 90% 以上的逻辑错误。

第二，在 pushup 和 pushdown 里加断言，检查 pre、suf、ans 是否满足 pre <= len、suf <= len、ans <= len。

第三，对于操作三，可以单独测试：先构造一个全是 1 的序列，执行一次操作三，然后查询目标区间，看填充结果是否符合预期。

6. 个人实操体会与扩展思考

这道题我前前后后写了三遍才完全过掉。第一遍错在 merge 函数的 pre 计算上，第二遍错在 fill 函数的递归边界，第三遍才把所有细节都理顺。我的体会是，区间合并类问题的难点不在于思路，而在于细节的精确性。每一个条件判断、每一个边界处理，都必须严丝合缝。

一个很实用的建议是：在写代码之前，先把 pushup、pushdown、merge、fill 这四个函数的逻辑用伪代码写清楚，特别是条件判断的部分。不要一边写一边想，那样很容易漏掉情况。

另外，这道题的扩展性很强。比如，如果把操作三改成“把区间内的 1 移动到另一段区间的最右边”，只需要把 fill 函数的递归顺序改成优先右儿子即可。如果把查询改成“最长连续 1”，只需要把 pre、suf、ans 的定义反过来，初始值也相应调整。掌握了一道题，一类题就都能做了。

最后分享一个小技巧：在写线段树的时候，我习惯把节点信息封装成结构体，并且给结构体写一个 merge 方法。这样 pushup 和 query 的合并逻辑可以复用同一份代码，减少出错概率。具体做法是：

struct Node { int pre, suf, ans, len, cnt0, lazy; Node merge(const Node &R) const { Node u; u.len = len + R.len; u.cnt0 = cnt0 + R.cnt0; u.pre = (pre == len) ? len + R.pre : pre; u.suf = (R.suf == R.len) ? R.len + suf : R.suf; u.ans = max(max(ans, R.ans), suf + R.pre); u.lazy = -1; return u; } };

这样 pushup 里直接调用 tree[p] = tree[p<<1].merge(tree[p<<1|1])，query 里直接调用 L.merge(R)，代码简洁很多，也不容易写错。这个习惯是我做了十几道区间合并题之后养成的，推荐你也试试。