刚把这道题调通趁着思路还热把从零到一的推导过程和踩过的坑完整记录下来。P15545「Stoi2037」晴天看起来名字很文艺实际上是一道非常典型的线段树区间合并题给你一排长度为 n 的城市位置每个位置标记为晴天1或雨天0然后支持两种操作——单点翻转天气以及查询某个连续区间里最长连续晴天的长度。如果你已经熟悉线段树的基本建树、单点修改、区间查询但第一次接触“线段树区间合并”这个套路那这题正好是一个承上启下的好练手如果你连线段树都还没入门建议先把基础模板过一遍再回来看这篇效果会好很多。1. 题目模型与核心题型识别1.1 题意转化先看清题目到底在问什么原题面大概率会用一段故事包装可能和“连续晴天天数”有关但拆掉修辞外壳后模型非常干净。假设有一个长度为 n 的 01 序列a[i] 1 表示第 i 个位置是晴天a[i] 0 表示雨天。接下来有 m 次操作每次操作二选一0 x把 a[x] 反转晴天变雨天雨天变晴天。1 l r询问区间 [l, r] 中最长的连续晴天天数也就是最长连续 1 的段长度。这里 n 和 m 的规模我按常见的 OI 出题习惯取 10^5 到 2×10^5 这个量级甚至更大。为什么特意强调数据范围因为范围直接决定了算法路线。如果 n 只有 100那直接暴力就行但如果 n 是 2×10^5暴力查询单次 O(n)最坏总复杂度 O(nm) 会到 4×10^10显然跑不动。再加上有单点修改说明我们需要一个能同时支持点修改和区间信息合并的数据结构。这个信息往台面上一摆线段树几乎就是标准答案。这里需要额外说一句题名里的“Stoi2037”大概率是这场比赛或者题目系列的名称而“晴天”只是这题的花名。我在做这类带文艺名字的题目时有一个习惯就是先完全无视故事背景只把输入输出和形式化定义抽出来。原因很简单故事是给题面增加可读性的不是给解题者增加负担的。你如果被“晴天”“雨天”这种词汇带跑想着按天气系统模拟反而容易把自己绕进死胡同。1.2 从暴力到数据结构的自然推理路径很多新手拿到这题会第一时间想能不能用前缀和前缀和确实能在 O(1) 时间内回答“区间内有多少个晴天”但这里问的是“最长连续晴天长度”也就是连续 1 的段最大长度。前缀和只能告诉你总数量无法告诉你这些 1 是怎么分布的。举个例子区间里有 5 个 1它们可能连成一段长度为 5也可能分成五段长度 1前缀和在这两种情况下给出完全相同的值所以这条路走不通。那二分答案行不行如果序列是静态的可以预处理所有晴天段的区间端点然后用二分在有序集合里找覆盖询问区间的段计算长度但是本题有单点修改每改一个位置晴天段的结构就会局部变化用有序集合维护段也能做甚至在某些情况下常数更小。不过线段树的优势在于它把所有信息揉进了一棵树上任何区间的查询都能通过 O(log n) 次节点合并得到思路统一代码结构也基本固定不容易出奇奇怪怪的边界问题。所以我最终选择的是线段树区间合并写法。2. 线段树解法设计与底层逻辑2.1 一个节点到底需要维护哪些值先回忆线段树的基本思想把区间不断二分每个节点管辖一段区间父节点的信息由两个子节点合并得到。本题的难处在于父节点的“最长连续 1 长度”并不能仅靠子节点的两个 mx 算出来。设想一个父区间 [l, r]它的最长连续 1 可能完全在左半边也可能完全在右半边还有可能跨越左右半边中间的分界线。前两种情况直接取左右子节点的 mx 就行麻烦的是第三种——跨越分界线的晴天段。为了算出跨越分界线的长度我们需要知道左子区间“从右端点开始向左最长能延伸多少个连续的 1”以及右子区间“从左端点开始向右最长能延伸多少个连续的 1”。这两段拼起来就是跨越分界线的最长连续 1 段。所以每个线段树节点需要维护四个值len当前节点覆盖的区间长度。pre从区间左端点开始向右连续 1 的最大长度。我习惯叫它“前缀连续 1”。suf从区间右端点开始向左连续 1 的最大长度。也就是“后缀连续 1”。mx整个区间内最长的连续 1 长度。单点修改时叶子节点只需根据当前 a[pos] 的值把 pre/suf/mx 设为 1 或者 0非叶子节点则递归更新完两个孩子后用 merge 合并信息。2.2 合并两个子区间时的核心公式这是整道题最关键的地方。假设我们拿到了左子节点 L 和右子节点 R要合并成父节点 C那么C.len L.len R.len。C.pre L.pre。如果左子区间全部都是 1L.pre L.len那么 C.pre 还能继续拼上 R.pre。C.suf R.suf。如果右子区间全部都是 1R.suf R.len那么 C.suf 还能继续拼上 L.suf。C.mx max(L.mx, R.mx, L.suf R.pre)。为什么 C.pre 只有在左子区间全为 1 时才能接上右子的 pre可以想象成两段绳子只有左边这段从头到尾连续不断你才能沿着它一直走到右半段的开头继续数如果左边这段数到一半断了前缀连续 1 就只能停在这个断点处和右边没关系。后缀的合并同理。这里给大家一个直观的“生活类比”把连续 1 看成一条完整的铁路线。左子区间的后缀就是从分界站向左数能连续通车的里程右子区间的前缀就是分界站向右连续通车的里程。父区间想要跨过中间这站形成一条更长的连续线路就必须保证左半边到分界站是通的右半边从分界站出发也是通的所以跨站线路长度就是 L.suf R.pre。至于整个区间最长线路要么纯在左半边要么纯在右半边要么从中间跨过去三者取最大就行。这一段就是整个 pushup 的思维核心。代码实现也不复杂Node merge(const Node L, const Node R) { if (L.len 0) return R; if (R.len 0) return L; Node C; C.len L.len R.len; C.pre L.pre; if (C.pre L.len) C.pre R.pre; C.suf R.suf; if (C.suf R.len) C.suf L.suf; C.mx max(L.mx, max(R.mx, L.suf R.pre)); return C; }注意最前面两行如果左边空返回右边如果右边空返回左边。这个边界处理特别关键后面查询时会多次用到。2.3 查询操作为什么不能直接返回一个整数在很多基础线段树题里查询函数返回的是区间最大值、区间和这类单一数值但这题不同查询 [l, r] 的答案必须经过多段合并才能得到。比如查询区间可能横跨线段树某节点的左右两个孩子你不能只拿左孩子的 mx 和右孩子的 mx 取 max因为答案可能跨过孩子的分界线。所以正确的做法是query 函数返回整个查询区间对应的 Node 结构体最后输出这个 Node.mx。具体流程是从根节点开始递归。如果当前节点的区间完全被查询区间覆盖直接返回当前节点的信息否则判断查询区间与左孩子、右孩子的交集分别递归查询最后把左右两个结果按顺序 merge 起来。这里顺序非常重要一定是左结果在前、右结果在后写成 merge(leftResult, rightResult)。如果写反了pre 和 suf 就会张冠李戴答案错误。实现时还需要处理“当前节点区间与查询区间没有交集”的情况。我在代码里用了一个约定无效节点返回 Node()它的 len 0。这样上层 merge 的时候第一行判断 L.len 0 就会直接返回另一个节点非常省事。但要注意默认构造函数必须把 len、pre、suf、mx 全部初始化成 0否则会用到野值。3. 完整代码实现与关键细节3.1 C17 参考代码下面是完整代码可以直接跑。这份代码我按洛谷常见风格来写输入输出用的 scanf/printf因为数据量到 10^5 级别后cin/cout 如果不同步关闭容易慢出问题。#include bits/stdc.h using namespace std; const int MAXN 200005; int n, m; int a[MAXN]; struct Node { int len; int pre, suf, mx; Node() : len(0), pre(0), suf(0), mx(0) {} }; Node merge(const Node L, const Node R) { if (L.len 0) return R; if (R.len 0) return L; Node C; C.len L.len R.len; C.pre L.pre; if (C.pre L.len) C.pre R.pre; C.suf R.suf; if (C.suf R.len) C.suf L.suf; C.mx max(L.mx, max(R.mx, L.suf R.pre)); return C; } Node tree[MAXN 2]; void build(int p, int l, int r) { if (l r) { tree[p].len 1; tree[p].pre tree[p].suf tree[p].mx a[l]; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); tree[p] merge(tree[p 1], tree[p 1 | 1]); } void update(int p, int l, int r, int pos) { if (l r) { a[pos] ^ 1; tree[p].pre tree[p].suf tree[p].mx a[pos]; return; } int mid (l r) 1; if (pos mid) update(p 1, l, mid, pos); else update(p 1 | 1, mid 1, r, pos); tree[p] merge(tree[p 1], tree[p 1 | 1]); } Node query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return tree[p]; int mid (l r) 1; Node L, R; bool hasL false, hasR false; if (ql mid) { L query(p 1, l, mid, ql, qr); hasL true; } if (qr mid) { R query(p 1 | 1, mid 1, r, ql, qr); hasR true; } if (!hasL) return R; if (!hasR) return L; return merge(L, R); } int main() { scanf(%d%d, n, m); for (int i 1; i n; i) scanf(%d, a[i]); build(1, 1, n); while (m--) { int op, x, y; scanf(%d, op); if (op 0) { scanf(%d, x); update(1, 1, n, x); } else { scanf(%d%d, x, y); printf(%d\n, query(1, 1, n, x, y).mx); } } return 0; }有人可能会问build 和 update 里叶子节点每次重新赋值 pre/suf/mx 时为什么不同时更新 len因为树节点数组是静态分配的并且 build 在递归到叶子时只会在每个叶子节点执行一次而 update 递归到叶子时是从一个已经构建好的树下来的当时的 len 一定已经被 build 设定好了所以不用反复写。不过如果你写代码时习惯保险一点在叶子节点里顺手写上 tree[p].len 1 也没问题不影响正确性。3.2 关于输入输出和常数优化的一些建议这道题的数据规模不算极端scanf/printf 已经足够。如果你平时习惯用 cin/cout记得在 main 开头加上 ios::sync_with_stdio(false); cin.tie(nullptr);否则在某些评测环境下可能会因为 IO 效率被卡掉几个点。线段树本身的操作次数是 O((nm) log n)单次递归常数不小但如果 n、m 都到 2×10^5总操作量大约几百万次递归不开 O2 也基本能过。需要注意的倒是别在不需要的地方用 vector 动态存储线段树静态数组 maxn 2 是更稳妥的选择。另外我推荐写一个辅助的对拍程序。手动构造小数据用暴力求解和线段树跑同样的操作随机生成几百组对比输出。这一步看起来麻烦但实际能帮你节省大量调试时间。尤其是区间合并题出错的概率往往不在算法思路上而在 merge 或查询返回值的顺序细节上人工肉眼盯代码很难看出来。4. 常见问题与调试实录4.1 查询时空节点处理不当导致答案变小我第一次写这个题时想的很简单query 递归中如果当前节点区间完全不在查询范围内直接返回 Node()。但问题来了默认构造的 Node 里 pre 0、suf 0、mx 0、len 0如果下一次 merge 没有处理 len 0 的情况把空节点和正常节点合并就可能出现一个诡异的组合空节点的 mx 是 0正常节点 mx 是 5max(0, 5, 0 0) 结果还是 5看起来没问题但空节点如果参与了 pre 的延伸计算比如空节点作为左孩子它的 pre 为 0可能会把右孩子的 pre 错误地压下去。这是隐患不是必然错误但稍不留神就会翻车。解决办法就是我在 merge 里加的两行if (L.len 0) return R; if (R.len 0) return L;这样能保证空节点在参与任何计算之前就被隔离既不污染 pre/suf也不会影响 mx。这也是我强烈建议在 merge 开头处理空区间的原因别指望每次查询都恰好避开空区间。4.2 合并顺序写反导致 pre/suf 错乱这是区间合并题最容易踩的坑。查询区间横跨左右孩子时假设左孩子区间是 [1,5]右孩子是 [6,10]查询 [3,8] 会递归得到左边部分和右边部分两个 Node。合并时如果写成 merge(R, L)整个语义就反了右孩子的前缀会被当成合并结果的前缀左孩子的后缀会被当成合并结果的后缀输出的 mx 也可能被错误拼接。这种 bug 在随机小数据上经常能暴露出问题但如果你测试的数据恰好跨度不明显可能意识不到。我自己的调试习惯是在 merge 调用前先用注释标注参数语义比如// merge(左边结果, 右边结果)确认每一次调用都符合这个约定。build 和 update 里也是同样顺序总是 merge(leftChild, rightChild)。这样统一后整个代码的逻辑压力会小很多。4.3 单点更新时忘记修改原数组这个 bug 特别隐蔽。我写过一版代码叶子节点的逻辑是tree[p].pre tree[p].suf tree[p].mx (tree[p].pre 0 ? 1 : 0);也就是说通过当前叶子节点的 pre 来判断旧值然后取反。这看起来没问题但这里种下了一个隐患如果连续两次更新同一个位置第一次更新后 a[pos] 已经变了第二次再来取反tree[p].pre 确实是新的值也能正确取反但假如未来有什么操作依赖了外部数组 a而 a[pos] 没同步更新就会产生不一致。最典型的是如果某个调试输出打印 a 数组和整棵树的叶子节点你会发现它们对不上。更合理的做法是维护一个独立的 a 数组更新时先 a[pos] ^ 1然后用新的 a[pos] 去刷新叶子节点。这份代码里我用的是正确写法a[pos] ^ 1; tree[p].pre tree[p].suf tree[p].mx a[pos];这种“外部数组与数据结构同步更新”的原则在做任何带修改的题时都值得养成习惯否则很容易在潜移默化中引入不一致。4.4 线段树数组开太小导致越界访问线段树空间如果静态声明为 tree[maxn 1]在一些边界情况会越界。经验法则是开 4 倍空间也就是 maxn 2。原因很简单对于一个长度 n 的区间构建线段树最坏情况下树的节点数量不会超过 4n。虽然 n 的下一级是 n 个叶子节点内部节点最多 n-1 个总数大概是 2n但递归建树时访问的下标可能超过这个理论值所以统一开 4n 最稳妥。你如果开 2n在 n 1 或极端非均匀拆分时可能越界这属于随机出现的隐性 RE很难查。4.5 查询边界出现 l r 的情况如果原题保证所有查询都有 l ≤ r那没问题但如果题目没有明确说明最好在 query 开头加一个判断如果 ql qr 直接返回空 Node。我自己的代码里默认了数据合法所以没加但实际做题时还是小心为上。尤其是数据结构题目输入数据的边界情况有时候会在第 3、第 4 个子任务中突然蹦出来坑你一下对付这类问题的唯一办法就是“宁可多写一个判断也不要等着评测机给你一个 WA 或 RE”。4.6 对拍调试技巧怎么快速定位问题如果你遇到 WA但数据点又很大肉眼根本看不出错在哪我习惯的做法是写一个 30 行的暴力脚本直接用数组原样维护每次操作更新数组查询时暴力扫一遍区间。然后随机生成 n 在 1 到 20、m 在 1 到 50 的小数据分别跑线段树和暴力一旦输出不一致就打印当前操作序列和两个答案的差异。这一步可以定位到具体是哪一次操作、哪一个区间出了问题再针对这个操作手动跟踪线段树递归路径。区间合并题用这个流程效率特别高因为大多数错误都是局部性错误一个具体的交叉区间就能触发。5. 这类题如何举一反三5.1 区间合并线段树的适用场景“晴天”这类题有一个明显特征询问的答案本质上是一个“结构信息”而不是单纯的“数值信息”。比如最长连续 1、最大子段和、最长连续上升段这些都需要合并左右孩子时额外维护前缀/后缀信息。掌握了这道题你会理解线段树不仅能维护加法、取 max 这种“可简单合并的量”还能通过设计适合的 Node 结构体维护更复杂的连续性问题。一个常见的变式是不加修改但每次询问的区间都是一个任意子区间。这个时候你也可以预处理 ST 表但 ST 表的合并逻辑和线段树几乎是同理的只是不支持修改。如果题目变成区间取反把一个区间内的所有 0 变 1、1 变 0那就需要在线段树上打懒标记同时维护区间内最长 0 段和最长 1 段取反时交换 0/1 的两套信息这比本题稍微复杂一些但底层思想完全一致。还有一个经典变式维护最长上升连续子串。你需要在节点里同时维护左右端点的具体值才能在合并时判断 left.suf 和 right.pre 是否可以拼起来。这题虽然不直接考这个但你会了这个套路以后遇到类似题目时第一反应就是“我该在节点里多存一个什么信息”而不是手足无措。5.2 从这题出发可以继续刷哪些题如果你想把区间合并这个套路练扎实可以找一些同类型的题来刷。经典的有区间最大子段和、最长连续递增子序列、以及一些带有“历史版本”或“区间翻转”的进阶线段树题。做的时候多注意比较这些题的节点定义和 merge 逻辑有哪些相似点有哪些不同点。比如区间最大子段和需要维护左端点开始的最大和、右端点结束的最大和、整段和、最大子段和这跟“晴天”的 pre/suf/mx 结构非常相似只是把“长度”换成了“和”把拼接条件从“全为 1”换成了“是否等于整段和”。实战中我还会刻意把多个题解放在一起对比比如网上有“glr-r4 芒种”的题解它也是一个带诗意的题名很多题解的着眼点都在“如何把字符串背景抽象成线段树维护的信息”。看看别人的代码里 merge 开头怎么处理空区间、查询时怎么避免顺序错误对自己写题会有很大帮助。5.3 关于做题心态的一个小建议像“晴天”这种题目构造非常巧妙但本质上就是一层窗户纸。没捅破之前你会在那里纠结怎么维护跨区间的连续长度感觉要额外存很多东西。捅破之后你会发现核心就是 pre 和 suf 两个字段。做这类题最大的收获不是这道题的 AC 代码而是在某次比赛或考试中你看到一个新的区间合并问题能迅速判断出“这题会不会用到左前缀和右后缀”然后少走很多弯路。我个人实际调试这道题最大的感受是区间合并题的坑基本上都出在 merge 的返回条件和查询合并顺序上。如果一开始就把 merge 边界写清楚写代码时会非常顺畅。这里分享一个很多老选手都在用的习惯新写一个线段树题时先把单个节点的结构体定义和 merge 函数写出来然后用三五个手写的小样例测一遍 merge 本身再把它嵌进整棵树的 build、update、query 中。这个习惯在区间合并题上尤其管用能省下大量在线段树上追 bug 的时间。希望这篇题解能帮你少踩几个坑顺利把这道“晴天”拿下。