UOJ170Picks loves segment tree VIII光看名字就知道又是一道线段树题。但这个系列能一路出到第八题考的东西肯定不只是区间和区间最值那么单纯。这道题把懒标记这个知识点几乎压榨到了极致——区间加、区间赋值、区间求和、区间最大值一拥而上任何一个标记的优先级没想明白最终答案就会错得莫名其妙。当年我在训练营里刷这道题调了整整一个晚上才把样例跑对第二天讲题复盘发现同组十来个人里有一大半都栽在同一个地方pushdown 里 set 和 add 的处理顺序。今天这篇文章就把这套东西从头捋一遍包括标记合并规则怎么推导、每段代码为什么长这样、以及我自己踩过的几个坑。如果你正在攻线段树进阶或者刷题刷到“多懒标记”这一关这篇应该能帮你省下不少走弯路的时间。1. 思路拆解这题到底在考什么1.1 表面是区间操作内核是懒标记优先级先快速对齐一下题面。这道题一般要求维护一个长度为 n 的数组支持四种操作区间加一个值、区间赋值成一个值、查询区间和、查询区间最大值。这套操作单独拎出来任何一个基础线段树都能轻松应付最多就是加一个懒标记往下传的事。但把它们放在一起之后一个节点上可能同时压着两种甚至两种以上的标记麻烦就来了。典型的场景是这样我先给某个大区间做了一个区间加标记还没往下推紧接着又给这个大区间的一个子区间做了赋值操作。那么碰撞点就出现了——父节点身上挂着“加了一个 v”的标记而子区间现在要被整体赋成另一个值这两件事到底谁覆盖谁答案取决于操作发生的先后。如果赋值操作发生在加法之后那么赋值应该把之前那些加法的效果整个盖掉。否则就会出现一个很滑稽的结果我先给你的区间加了 5后来让你整体变成 100最后算出来单个元素却是 105。这显然不对105 的意思是“旧值加 5 之后再变成 100 的 5 被保留了”但我们想要的是一次彻底的重置。所以这道题真正要考的是你能不能给一堆懒标记定义出清晰且自洽的合并语义并在 pushdown 时严格按这个语义执行。代码本身并不长难的是把每一步之间的逻辑关系理顺。1.2 别急着写代码先想清楚标记合并规则很多新手拿到这道题的第一反应是我给节点加一个set标记再来一个add标记pushdown 的时候两个都往下传不就行了真这么简单的话这题就不会挂在 UOJ 上让那么多人半夜抓耳挠腮了。问题出在“两个都往下传”这句话上。假设父节点的标记状态是set 100, add 5含义是这个区间先被赋成了 100然后又整体加了 5。把这个标记传给儿子节点时儿子的旧标记应该怎么处理一个常见的错误是儿子的add直接加上 5但儿子的set标记还被保留着。害如果儿子之前身上也有set 50, add 7这一通操作下来不就变成了“先设 50、再加 7、再设 100、再加 5”四层变换大杂烩了吗逻辑完全搅在一起。正确的做法是分两种情况讨论。第一父节点有set标记说明父节点曾经对整段区间做过一次赋值操作。那么在这次赋值发生时儿子节点身上不管存着多少历史标记全部作废。赋值之后再统一加一个add。所以儿子节点的最终标记状态应该是set 父节点.set, add 父节点.add。第二父节点只有add标记没有set那说明父节点区间只是在原有基础上整体偏移儿子的set标记可以保留add标记累加即可。这套规则一开始可能觉得绕其实用生活类比一下就通了set相当于“清空整张画布重新画”add相当于“给画布上所有颜色统一调亮一个亮度”。一旦你重新画了底稿之前的调亮效果自然就没了。只有没重画的时候调亮才会叠加到旧画上。想通了这一点后面的代码实现就是一马平川。如果这个优先级没想明白pushdown 里每写一行代码都是地雷。2. 核心难点set 和 add 两个标记的博弈2.1 节点里到底该存哪些状态动手写代码之前先把节点结构定义清楚。这一题我用的节点信息包括四个字段sum表示区间和mx表示区间最大值add表示加法懒标记setv表示赋值懒标记。setv这里有个 trick它需要一个特殊值来表示“当前节点没有赋值标记”。因为真实的赋值操作可能把区间赋成任意整数如果直接用 0 当“无标记”刚好遇到赋值成 0 的操作就完蛋了。我习惯用一个极大值比如const ll INF (1LL 60)来当哨兵。只要题目保证操作数值的绝对值远小于这个值就不会发生冲突。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 200005; const ll INF (1LL 60); struct Node { ll sum, mx; ll add; // 加法懒标记 ll setv; // 赋值懒标记等于 INF 表示没有赋值 } tr[MAXN 2]; ll a[MAXN]; void pushup(int p) { tr[p].sum tr[p 1].sum tr[p 1 | 1].sum; tr[p].mx max(tr[p 1].mx, tr[p 1 | 1].mx); }pushup很简单左右儿子合并即可。不过要注意tr[p]自己的懒标记是什么不影响pushup的合并因为tr[p].sum和tr[p].mx存的是已经包含当前节点懒标记作用之后的值合并时直接用即可。2.2 合并规则为什么是这样现在推导两个更新操作在节点上的作用方式。这个推导过程是我觉得整道题最关键的地方强烈建议你自己在草稿纸上也推一遍别看完了就以为会了。先说区间加操作。对某个完全被覆盖的节点执行区间加 v 时这个节点的sum要加v * 区间长度mx要加 v然后把这个 v 累加到add标记上。如果节点之前没有setv那很好标记就只是add变大了一点。如果节点之前有setv说明这个节点现在记录的是“先被赋成 setv然后又经历了一些加法”。此时区间加应该继续叠加在加法上而setv保持不变。void add_update(int p, int l, int r, int ql, int qr, ll v) { if (ql l r qr) { tr[p].add v; tr[p].sum (ll)(r - l 1) * v; tr[p].mx v; return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) add_update(p 1, l, mid, ql, qr, v); if (qr mid) add_update(p 1 | 1, mid 1, r, ql, qr, v); pushup(p); }再说区间赋值操作。这个更干脆——既然整个区间都被重置成一个新值那么这个节点之前积压的add和setv统统没有意义了。所以执行赋值时直接设setv v同时清空add并且把sum改成v * 区间长度mx改成 v。这里的“清空 add”是必写的漏掉的话就会出现“赋值之后还残留旧加法”的灵异现象。void set_update(int p, int l, int r, int ql, int qr, ll v) { if (ql l r qr) { tr[p].setv v; tr[p].add 0; // 这一步清零非常重要 tr[p].sum (ll)(r - l 1) * v; tr[p].mx v; return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) set_update(p 1, l, mid, ql, qr, v); if (qr mid) set_update(p 1 | 1, mid 1, r, ql, qr, v); pushup(p); }注意add_update里我没有清空setv因为“先 set 再 add”的语义是合法的。而set_update里必须清空add因为一个新建的set会覆盖掉之前所有的加法历史。这一对操作看起来对称实际上完全不对称恰恰是这题最容易写错的地方。2.3 pushdown 的顺序就是生命线pushdown是整个线段树的发动机也是最容易翻车的地方。前面说过如果父节点存在setv那么子节点所有的旧标记都要作废整体变成“父节点 setv 的值 父节点 add 的偏置”如果父节点没有setv那只需要把add累加到子节点上。所以正确的pushdown顺序是先处理setv把子节点的setv覆盖掉、add清零再叠加父节点的add。如果先处理add再处理setv就会把父节点的加法错误地应用到“set 之前的旧世界”上最后 set 又把 add 的效果覆盖掉加法直接丢失。void pushdown(int p, int l, int r) { int mid (l r) 1; int lc p 1, rc p 1 | 1; if (tr[p].setv ! INF) { ll v tr[p].setv; tr[lc].setv v; tr[lc].add 0; // 清掉儿子之前积累的 add tr[lc].sum (ll)(mid - l 1) * v; tr[lc].mx v; tr[rc].setv v; tr[rc].add 0; tr[rc].sum (ll)(r - mid) * v; tr[rc].mx v; } if (tr[p].add ! 0) { ll v tr[p].add; tr[lc].add v; tr[lc].sum (ll)(mid - l 1) * v; tr[lc].mx v; tr[rc].add v; tr[rc].sum (ll)(r - mid) * v; tr[rc].mx v; } tr[p].add 0; tr[p].setv INF; }这段代码里最容易被忽略的是tr[lc].add 0这一行。很多新手在 set 分支里只改了setv、sum、mx忘了把儿子旧的add清零结果就是儿子节点里残留下了“设定值之前的偏移量”下面更新的数据全被污染。你可以把这个模式记成一句口诀赋值清零加法叠加下推先赋值后加偏置。每次写 pushdown 之前默念一遍能少踩一大半的坑。3. 完整实现从 build 到 query 一步步写3.1 建树与初始化建树的时候每个节点的setv都要初始化为INFadd初始化为 0。叶子节点直接读入数组值内部节点靠pushup合并。void build(int p, int l, int r) { tr[p].add 0; tr[p].setv INF; if (l r) { tr[p].sum tr[p].mx a[l]; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); pushup(p); }这里有个容易踩的细节如果是在多组测试数据里跑每次新建Node结构体数组时setv默认值不是安全的INF。我习惯在build里显式赋值或者每组数据前用循环把setv置成INF避免上一组数据的残留标记影响这一组。尤其是用结构体数组而不是vector的时候这种“脏数据”问题特别隐蔽。3.2 查询操作的实现查询区间和、区间最大值时如果当前节点被查询区间完全覆盖直接返回sum或mx。否则需要先pushdown把父节点积压的懒标记传给儿子再递归查询左右子树。ll query_sum(int p, int l, int r, int ql, int qr) { if (ql l r qr) return tr[p].sum; pushdown(p, l, r); int mid (l r) 1; ll res 0; if (ql mid) res query_sum(p 1, l, mid, ql, qr); if (qr mid) res query_sum(p 1 | 1, mid 1, r, ql, qr); return res; } ll query_max(int p, int l, int r, int ql, int qr) { if (ql l r qr) return tr[p].mx; pushdown(p, l, r); int mid (l r) 1; ll res -INF; if (ql mid) res max(res, query_max(p 1, l, mid, ql, qr)); if (qr mid) res max(res, query_max(p 1 | 1, mid 1, r, ql, qr)); return res; }还有一个容易忽略的点查询时如果父节点有懒标记但你没 pushdown儿子节点里存的sum和mx可能是完全没有应用父节点标记的旧值这时候查出来的结果就会比正确值小或者大。所以只要之后还要往下走就必须先pushdown哪怕add是 0、setv是INF也不会有额外开销问题代码里我加了非零判断能省一点是一点。3.3 完整题解串起来的流程把上面四段拼在一起就是一个完整可提交的线段树。实际做题时输入大概是 n 个初始元素和 q 次操作每次操作根据 op 的类型调用不同函数。这里给一个简单主流程示例int main() { int n, q; scanf(%d%d, n, q); for (int i 1; i n; i) scanf(%lld, a[i]); build(1, 1, n); while (q--) { int op, l, r; scanf(%d%d%d, op, l, r); if (op 1) { // 区间加 ll v; scanf(%lld, v); add_update(1, 1, n, l, r, v); } else if (op 2) { // 区间赋值 ll v; scanf(%lld, v); set_update(1, 1, n, l, r, v); } else if (op 3) { // 查询区间和 printf(%lld\n, query_sum(1, 1, n, l, r)); } else { // 查询区间最大值 printf(%lld\n, query_max(1, 1, n, l, r)); } } return 0; }注意所有与区间长度相乘的地方都要先把区间长度转成long long因为(r - l 1) * v如果左边是 int右边是long long虽然 C 会做隐式提升但如果你在一个项目里开了比较严格的编译选项或者恰好区间长度是 int、v 接近1e18就可能有溢出风险。稳妥起见所有乘法的左操作数都显式转ll。4. 实战排查新人最容易踩的四个坑4.1 set 之后 add 没清空赋值操作“灵气附体”这是我见过最多的情况。症状是对某个区间赋值后再对这个区间的子区间做加法结果答案里凭空多出了一个更早时候的 add 偏移量。比如初始全是 0先对 [1,5] 加 100然后对 [1,5] 赋值为 7。如果set_update里没清add节点的状态会变成setv 7, add 100。之后一旦 pushdown子节点先被设成 7 又被加上 100最后得到 107。这显然不对因为赋值操作应该把之前的 100 完全抹掉。排查方法很简单在set_update里设一个断点检查节点旧的add是否为 0。一旦发现赋值时add不是 0基本就可以确定是这里少了一行清零。4.2 pushdown 顺序写反导致加法丢失或错乱如果你在 pushdown 里先处理add再处理setv会得到两种典型错误。第一种情况父节点同时有setv和add先传add再传setv最终儿子节点的add被清掉、setv被覆盖父节点原本要叠加的加法全部丢失。第二种情况父节点只有setv没有add顺序反了倒没什么影响这就导致错误很难在小样例里第一时间暴露。我的排查经验是造一组“故意为难”的数据比如先对区间赋值再对同一个区间做几次累加接着马上查询子区间。如果查询结果比预估值少了一个加数优先怀疑 pushdown 顺序。这种问题靠肉眼盯代码很难看出来用对数器对拍是最快的定位方式。4.3 边界值与数据类型处理setv的哨兵值选不好会带来一系列隐性问题。我之前用0x3f3f3f3f当哨兵结果某道题操作值最大能到1e9差点撞上。后来干脆统一用1LL 60只要题面数值范围在1e18以下就绝对安全。还有如果题目要求查询区间最大值初始化res -INF时也要用足够小的负数不能用 0否则全负序列查询最大值会直接错。另一个常见问题是long long溢出。当 n 高达2e5而且一个区间被反复addsum累加值可能会超过int范围所以所有存数值的字段必须是long long。我的习惯是和值有关的量全部long long只在操作类型和区间端点用int一刀切最省心。4.4 一个通用的对拍调试法写线段树题我不会只靠样例判断正确性。样例能过说明不了任何问题大概率只是没覆盖到标记交互的边界。我的习惯是写三个文件一个暴力模拟的bf.cpp一个线段树版本的seg.cpp一个随机数据生成器gen.cpp。然后写一个无限循环脚本每次生成小规模随机数据分别跑两份代码比对输出。数据生成器里要刻意让操作集中在同一个区间上这样更容易触发标记堆积。比如l, r经常随机成整个区间的子集并且交替执行赋值和加法操作。小数据规模比如 n 10, q 100 的时候暴力程序跑得飞快对拍几百组就能把大多数逻辑问题揪出来。对拍脚本虽然写起来简单但它是省时间的神器。尤其是这类“样例看不出错、大数据又不知道对不对”的懒标记题没有对拍的话几乎只能靠玄学调参有了对拍之后定位问题基本就是十分钟内的事。我自己后来回过头看这道题最大的收获反而不是那几行 pushdown 代码而是养成了一个习惯处理任何一种“带优先级的多懒标记”问题先拿纸笔定义清楚每个标记的语义再考虑怎么合并、怎么下推。线段树的代码技巧翻来覆去就那么几个真正拉开差距的是思路的清晰程度。如果哪天遇到一道题操作里多了区间乘你再回头看这里就会更有感触——无非是把“乘法优先、加法后置”的优先级再排一遍节点里多维护一个mul标记而已。理清了这道题的套路后面再难的线段树变种也都能稳住阵脚。