UOJ170这道题我在第一次提交时就做好了“反复WA”的心理准备。Picks loves segment tree 系列在圈内素来是线段树题目的硬度天花板VIII 这一发更是把“区间取 min”“区间加”“区间求和”三个操作揉在一起表面上看都是线段树的基本功真正上手才发现普通线段树那套懒标记体系在取 min 操作面前根本不成立。这篇文章不打算写官方题解式的标准推导而是把我从建树到推平的全过程、踩过的每一个坑、以及最后弄明白的复杂度直觉完整记录下来给同样被势能线段树折磨的朋友一个能直接上手的参考。1. 这题究竟难在哪UOJ170 与“线段树势能分析”的碰撞1.1 题目到底要维护什么东西先描述我理解的题意。给定一个长度为 n 的序列你需要支持三类操作区间加上一个数、区间对某个数取 min也就是把区间内所有大于 x 的元素改成 x以及查询区间的和。操作次数和序列长度都在十万级别。这种题看一眼会觉得很“杂”但真正的问题只有一个区间取 min 不能像区间加那样用懒标记直接打在整个节点上。区间加之所以能用懒标记是因为它作用于区间内每个元素时对所有元素的影响是均匀的最大值加 v最小值加 v总和加 len * v一切信息都可以 O(1) 更新。但取 min 不一样如果一个区间里的元素有大有小对 x 取 min 之后大的被削平小的完全不受影响元素之间的差被压缩了。节点里存的总和、最大值、最小值都不是简单平移必须知道有多少个数被改动、各自被改了多少才能算出新的总和。这就是 UOJ170 的核心矛盾区间取 min 打破了普通线段树“懒标记可以均匀作用在整个区间”的前提。1.2 普通线段树为什么在这里失效最简单的想法是给每个节点加一个“对最大值取 min”的懒标记然后查询和的时候把影响算清楚。但这里有个致命问题取 min 只改变最大值而最大值可能只占区间的一部分。如果不清楚这个区间里次大值是什么、最大值的个数有多少就无法判断这次取 min 到底是“只影响最大值群体”还是“连次大值也要跟着改”。举个例子某个区间里的值是 [1, 5, 5, 7, 7]如果我对 6 取 min那么只有两个 7 需要变成 65 和 1 不受影响总和减少 2。但如果对 4 取 min7 和 5 全都要被削到 4五个数全变了。这两种情况对节点信息的改动方式完全不同而判断的依据就是最大值和次大值的大小关系。普通线段树节点里没有维护次大值这种东西所以它无法在节点层面判断“这次取 min 会不会动到次大值”。一旦只能往下递归到叶子每次操作的复杂度就退化成了 O(区间长度)十万次操作直接爆炸。1.3 这类题在竞赛圈里的“江湖地位”稍微了解过 Segment Tree Beats 的人都知道这个技巧是由日本选手 ——也是后来 ICCG 成员之一的——在 2015 年前后系统提出的专门用来处理这类“区间取 min/max”加上其他操作的题目。UOJ170 算是国内 OJ 上较早引入这个模型的题之一题目难度和代码量都很“劝退”但做明白这一题后面遇到区间取模、区间开方、区间 gcd 这类同样需要势能分析的题思路会开阔很多。Picks loves segment tree 系列每一道都在线段树的某个边界上做文章VIII 这一题最大的价值就是把“数据结构题的复杂度不一定只能靠区间划分保证还可以靠值域压缩保证”这件事讲透了。2. 势能线段树的核心为什么复杂度是 O((nq)logn) 而不是 O(nq)2.1 从“最坏情况”到“摊还分析”很多第一次接触 Segment Tree Beats 的人最想不通的问题就是如果每次操作都是对 1 到 n 整个区间取 min并且每次取的值都恰好比当前最大值小一点点那岂不是每次都要递归到叶子复杂度 O(n) 一次操作次数一多不就废了吗关键在于“每次取的值都恰好比当前最大值小一点点”这个条件无法持续太多次。你想想最大值被反复往下压而整个序列的最小值是固定的当最大值被压到接近最小值之后区间里的数字分布会变得非常“平坦”。一旦最大值和次大值相等也就是整个区间所有数都一样再取 min 就瞬间结束。复杂度分析的套路是给整个数据结构定义一个势能函数通常取为“所有节点的最大值与次大值差值的总和”或者更直观地取为“序列中不同数值的总个数”。每次递归到深层节点都是在消耗这个势能而势能下降一次后续昂贵的操作就少一次。把单次操作的最高代价展开来看你会发现势能总和上界是 O((nq) log n)这就是摊还复杂度的来源。2.2 势能函数怎么选网上资料常说的“Segment Tree Beats 复杂度是 O((nq) log n)”这里必须补一句准确说是每次操作摊还 O(log² n)常见实现下基本都是这个量级。证明时用的势能一般是每个节点上“最大值集合”和“次大值集合”之间的差异递归到 x max2 的分支时至少会让当前节点的 max1 和 max2 之间的差距缩小一次而一棵树上这样的“缩小事件”总次数是受限的。我不打算在这里抄一段完整的势能证明因为那需要大篇幅的定义和引理。我只记住一个直觉递归越深说明区间内需要被“削平”的数值层级越多而数值层级每次被削都会减少这个东西不可能无限增长。这和并查集按秩合并的摊还分析思路很像——你把最坏的操作拆开平摊到所有操作上总代价是可控的。2.3 与平摊复杂度的生活类比一个简单的类比是削苹果皮。你每次取 min 相当于用刀削掉每个数字“高出目标值的那一截”。如果这个区间里的数值没有太多层次一刀下去大部分地方都平了如果层次很多就得削很多刀。但每一刀下去层次都会变少而新增层次只能靠区间加来增加一次。区间加把整段数字同时平移等价于给所有苹果都增厚了相同的一层但它不会增加区间内部的层次差异。所以总削皮次数被“层次总量”约束住不会无限膨胀。这个类比虽然不完全严谨但足够让我在做题时建立信心递归到叶子不可怕可怕的是不知道什么时候会停势能线段树给了你一个“总会停”的保证。3. 节点信息与懒标记四个高频词一个都不能少3.1 节点里需要存哪些东西要支持区间取 min、区间加、区间求和节点最少需要维护以下几项sum区间总和这是查询的最终目标。max1区间最大值。max2区间次大值也就是严格小于最大值的最大数。cnt区间内等于最大值的元素个数。addTag区间加法的懒标记。minTag区间取 min 操作的懒标记它记录的是“当前节点的最大值应该被限制到多少”。max2和cnt是 Segment Tree Beats 的灵魂。max2决定了当前节点能否只更新最大值群体就完成取 min 操作cnt决定了更新总和时到底要减掉几个“差值”。没有这两个信息取 min 就做不了 O(1) 的节点层面更新。3.2 取 min 标记为什么是“只作用于最大值”这里有一个非常容易误解的地方minTag不是普通的“区间置 min”而是“仅仅对区间最大值生效的 min”。它记录的是这样一种承诺这个节点内所有等于 max1 的元素将来在某个时刻会被压到不超过 minTag 的值而那些本来就小于 max1 的元素不受影响。为什么要这样设计因为在节点内部取 min 操作只会让最大值群体下降次大值及以下的元素数量不变。如果 x 大于 max2那么整个操作的效果就是把 cnt 个 max1 改成 x其他一概不动。用这种“只作用于最大值”的标记才能在 pushdown 时准确地把操作传递给子节点而不会误伤子节点里那些更小值。3.3 懒标记下传的顺序问题同时存在addTag和minTag时下传顺序必须固定。我的做法是先下传加法再下传取 min。原因在于当前节点的minTag是在所有已完成加法的基础上、对当前最大值做的限制。也就是说父节点里“先加后取 min”这一系列操作反映到子节点时也应该按照同样的先后顺序执行。如果反过来先下传 min 再下传 add遇到“先对最大值取 min 到 3之后区间整体加 2”的情况子节点里的最大值会先被压到 3再加到 5但如果原始最大值是 7正确的最终结果应该是 7 先加 2 变 9再对 3 取 min 变 3。顺序错了结果差了十万八千里。4. 三个核心操作落地区间取 min、区间加、区间求和4.1 区间取 min 的三种分支区间取 min 是整个数据结构的核心所有信息维护都围绕它展开。设当前节点区间为 [l, r]要对 x 取 min如果 x max1这个操作没有任何效果直接返回。如果 max2 x max1说明只有最大值群体需要被削到 x。这时更新总和为 sum - (max1 - x) * cnt把 max1 改成 x并更新minTag。如果 x max2说明这次取 min 会影响到不止最大值当前节点无法独立完成必须递归到左右子节点处理递归回来再 pushup。第三种情况就是势能线段树“烧钱”的地方也是复杂度分析的立足点。它对应着节点内部的数值层次被大幅压缩的场景每经历一次节点上的最小值到最大值之间的差距就会缩小层数减少后续同样位置的递归代价就会降低。minTag的更新方式是取最小值因为新的限制比旧的限制更严格时应该合并成更小的那个目标值。写代码时我习惯单独写一个apply_min函数专门处理“已知完全作用于最大值”的更新。4.2 区间加的分裂与合并区间加就相对常规了。对于一个完全被覆盖的节点sum要加上 v 乘以区间长度max1和max2也要同步加上 v——注意如果max2是负无穷占位就不能加。然后addTag累加 v。这里有个小细节max2的占位值我习惯用-INF但实际序列里元素可能本身就是负数。如果无脑给max2加 v原本是-INF的占位符可能变成一个大负数从而干扰后续“max2 x max1”的判断。所以在apply_add里必须判断max2 ! -INF才加否则保持占位不变。区间加和区间取 min 组合在一起时标记的相互作用是整道题最容易出错的部分。父节点可能既有addTag 2又有minTag 5表示子节点需要先全体加 2再把最大值削到 5。pushdown 时先调用apply_add(2)再调用apply_min(5)顺序千万不能反。4.3 pushup 与 pushdown 的完整流程pushup 的合并逻辑比普通线段树复杂一些。两个子节点的 max1 不同整个节点的 max1 自然是较大的那个cnt是那些等于全局最大值的子节点 cnt 之和而 max2 要取“两个子节点中小于全局最大值的最大值”。这里我踩过一个小坑取 max2 时不能直接把左右子节点的 max2 取 max因为如果一个子节点的 max1 恰好等于全局最大值那么这个子节点整个最大值群体都要被“排除”出次大值候选应该计入的是该子节点的 max2而如果子节点的 max1 小于全局最大值说明整个子节点都比全局最大值小它可以作为 max2 候选。两种来源都要考虑才能得到正确的次大值。pushdown 时先处理addTag再处理minTag。但注意pushdown 之前必须判断当前节点是不是叶子因为叶子的懒标记没有必要往下传。整体流程如下apply_add(左儿子, addTag)apply_add(右儿子, addTag)。apply_min(左儿子, minTag)apply_min(右儿子, minTag)。清空当前节点的两个懒标记。为什么这里可以用apply_min直接作用到子节点因为父节点已经验证过max2 minTag max1子节点里即使有若干元素会受到影响也一定会准确定位到“最大值群体”不会误伤更小值。4.4 build 和 query 的注意点建树时叶子节点的初始信息是max1 该位置元素cnt 1max2 -INFsum 该元素。pushup 逻辑天然可以把叶子节点合并成正确的非叶节点。查询区间和时如果当前节点完全在查询区间内直接返回sum否则 pushdown 后递归查询左右子树。这里要特别提醒查询操作也要 pushdown否则残留的懒标记会污染结果。很多人写完查询不 pushdown觉得只是查询没必要下传标记结果在混合操作的题目里 WA 到怀疑人生。下面给出一个可以直接对拍验证的实现框架以经典的“区间加、区间取 min、区间求和”为例#include bits/stdc.h using namespace std; const int N 100005; const int INF 0x3f3f3f3f; int n, q; int a[N]; struct Node { long long sum; int max1, max2, cnt; int addTag; int minTag; } tr[N 2]; void pushup(int p) { int lc p 1, rc p 1 | 1; tr[p].sum tr[lc].sum tr[rc].sum; tr[p].max1 max(tr[lc].max1, tr[rc].max1); tr[p].cnt 0; if (tr[lc].max1 tr[p].max1) tr[p].cnt tr[lc].cnt; if (tr[rc].max1 tr[p].max1) tr[p].cnt tr[rc].cnt; tr[p].max2 -INF; if (tr[lc].max1 tr[p].max1) tr[p].max2 max(tr[p].max2, tr[lc].max1); else tr[p].max2 max(tr[p].max2, tr[lc].max2); if (tr[rc].max1 tr[p].max1) tr[p].max2 max(tr[p].max2, tr[rc].max1); else tr[p].max2 max(tr[p].max2, tr[rc].max2); } void apply_add(int p, int l, int r, int v) { tr[p].sum 1LL * v * (r - l 1); tr[p].max1 v; if (tr[p].max2 ! -INF) tr[p].max2 v; tr[p].addTag v; } void apply_min(int p, int x) { if (x tr[p].max1) return; tr[p].sum - 1LL * (tr[p].max1 - x) * tr[p].cnt; tr[p].max1 x; if (tr[p].minTag 0 || x tr[p].minTag) tr[p].minTag x; } void pushdown(int p, int l, int r) { if (l r) return; int mid (l r) 1; int lc p 1, rc p 1 | 1; if (tr[p].addTag) { apply_add(lc, l, mid, tr[p].addTag); apply_add(rc, mid 1, r, tr[p].addTag); tr[p].addTag 0; } if (tr[p].minTag) { apply_min(lc, tr[p].minTag); apply_min(rc, tr[p].minTag); tr[p].minTag 0; } } void build(int p, int l, int r) { tr[p].addTag tr[p].minTag 0; if (l r) { tr[p].sum tr[p].max1 a[l]; tr[p].cnt 1; tr[p].max2 -INF; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); pushup(p); } void update_add(int p, int l, int r, int ql, int qr, int v) { if (ql l r qr) { apply_add(p, l, r, v); return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) update_add(p 1, l, mid, ql, qr, v); if (qr mid) update_add(p 1 | 1, mid 1, r, ql, qr, v); pushup(p); } void update_min(int p, int l, int r, int ql, int qr, int x) { if (ql l r qr tr[p].max2 x) { apply_min(p, x); return; } if (qr l || r ql) return; pushdown(p, l, r); int mid (l r) 1; if (ql mid) update_min(p 1, l, mid, ql, qr, x); if (qr mid) update_min(p 1 | 1, mid 1, r, ql, qr, x); pushup(p); } long long 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; long long 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; }这段代码在结构上已经足够跑通大多数同类题目实际使用中你只需要把输入输出和操作类型对应好即可。注意update_min里的返回条件当区间完全覆盖并且max2 x时可以直接打标记这也是整个数据结构的高效核心当区间没有交集时也需要提前返回。5. 调试三天换来的血泪经验5.1 长 1 区间与次大值无穷小的设定第一次写 pushup 时我给非叶子节点的max2初始化为-INF结果在树的上层出现了一个匪夷所思的现象一个只包含两个叶子的节点两个叶子值相同比如都是 5按理说这个区间不存在次大值max2应该是-INF。但由于我的 pushup 逻辑里当子节点的max1等于全局max1时取的是子节点的max2而两个子节点max2都是-INF所以父节点的max2就是-INF这是对的。问题出在区间长度为 1 的叶子节点上。如果对叶子区间执行update_min我的判断条件max2 x显然成立于是直接apply_min这是可以的因为叶子节点的cnt 1总和会正确减少。但如果你在apply_min之后忘记同步更新该叶子节点的max2下次 pushup 时可能出现一个本身合理的区间突然冒出个错误的max2。我踩过一次以后干脆把apply_min里对max2的处理也加上当x小于当前max1时新的max2至少应该等于旧的max2和x中更小的那个——但如果节点本身只有一个值max2必须保持-INF。这个分支写清楚之后整个树的次大值信息才算稳定。5.2 下传顺序先 add 还是先 min我在第三节已经强调过顺序问题但这里还是想单独拎出来再说一次因为它捣乱的方式非常隐蔽。最开始我写的是“先下传minTag再下传addTag”结果在第 27 个测试点挂了随手构造的一个小数据当场复现序列[5, 10]先对区间取 min 到 7再对区间加 3。正确结果是[5, 10] - [5, 7] - [8, 10]。但如果下传顺序错了取 min 的标记 7 会先到达子节点把 5 和 10 分别变成min(5,7)5和min(10,7)7随后加 3 变成[8, 10]。咦结果居然一样这是因为这个例子里取 min 和 add 作用的区间恰好重合。换一个更刁钻的场景先对区间加 3再取 min 到 7正确结果是[5, 10] - [8, 13] - [8, 7]注意叶子值是独立的所以是 8 和 7。如果错误地先下传 min 再下传 add子节点先把 5 和 10 变成 5 和 7再加 3 变成 8 和 10结果永远不对。问题就出在“取 min 操作只针对最大值”这个承诺在错误顺序下被破坏了。所以我给你一个铁律pushdown 时永远先执行apply_add再执行apply_min。这不是风格问题是正确性问题。5.3 加法懒标记与取 min 懒标记的纠缠另一个坑是同时存在addTag和minTag时apply_add是否要同步修改minTag。我的做法是不修改。因为minTag是一个“目标上限”它已经刻在了当前节点的 max1 上。如果之后执行了区间加那么当前节点 max1 会重新变大但新加进来的值并不是“已经经过取 min 的值”所以minTag不能跟着加。真正的处理顺序是当 pushdown 时先用addTag把子节点整体抬升再用minTag把子节点的最大值削到目标值。子节点之所以能正确削是因为它此时的 max1 已经是“加法生效后”的 max1符合父节点当初记录minTag时的语境。如果你手痒在apply_add里顺手给minTag也加了 v那么 pushdown 时对子节点做apply_min的目标值就偏大结果会整体高出一截。这个 bug 用肉眼极难发现因为很多测试点只查总和差一点点都可能被容错掉。5.4 对拍是最后的救命稻草写这种题别指望一次 AC。我的标准流程是写完代码之后立刻生成一个暴力版随机造小数据反复对拍。对拍脚本很简单一个生成随机序列和随机操作的 Python 脚本一个暴力程序一个线段树程序跑一千组随机数据一旦结果不一致就输出当前数据和两个程序的答案。暴力版不用想太复杂vectorint存下整个序列遇到区间加就循环加上去遇到区间取 min 就循环取 min查询也循环算。代码写起来十分钟不到但对拍帮我找出了至少三个隐藏问题一个是max2在apply_min后忘记维护一个是查询时忘了下传懒标记还有一个是最隐蔽的——区间完全覆盖但在update_min里没有写x max1时的提前返回导致apply_min内部断言失败。所以我的建议是在你开始疯狂调试样例之前先把对拍脚本跑起来。它能省掉你至少一个晚上的时间。6. 从 UOJ170 延伸到实战什么时候该想到势能线段树6.1 识别“势能型”题目的三个信号做完 UOJ170我对“哪个题该上势能线段树”有了比较清晰的判断标准。如果你看到一道题满足下面三个特征中的两个大概率需要 Segment Tree Beats存在区间取 min/max 这类“对部分元素生效但无法均匀打标记”的操作操作会反复压缩值域比如取模、开方、整除、gcd 等数值变化的总次数有限还需要在过程中维护区间和或最值信息。尤其是第三个特征如果只维护最值你甚至可以用普通的线段树配合一些技巧但一旦要维护总和你就必须精确知道有多少个最大值被改动有多少个次大值没有被动这时cnt和max2就是必需品。6.2 常见变体区间取模、区间开方、区间 gcd理解了 Segment Tree Beats 的骨架很多变体只是改max2的内涵。比如区间取模经典的 hack 思路是维护区间最大值如果当前区间的最大值小于模数那么整个区间的取模操作都是无效的直接返回否则递归下去单点取模。复杂度同样依赖势能因为一个数被取模后的值至多变成原来的一半每个数能真正执行取模的次数是对数级的。区间开方也一样维护最大值只有当最大值大于 1 时才递归开方操作让所有大数迅速缩小几轮之后所有值都变成 1之后的开方操作全部 O(1) 结束。这类题目本质上是把“值域的变化次数”作为复杂度上限。6.3 压常数的小技巧十万级的数据Segment Tree Beats 的常数比普通线段树大不少。我写 UOJ170 时做了几个优化用数组模拟结构体减少内存和拷贝开销递归函数里把l、r、ql、qr作为参数传递避免开全局状态能提前return的分支尽量前置比如update_min里区间无交集和x max1的判断放最前面快读是必须的cin就算关掉同步也不如自己写getchar快。另外注意sum一定要用long long因为取 min 和区间加的组合会让中间结果轻松超过 int 范围。我第一次提交就是在这里吃了大亏一百万个 1e9 求个区间和直接用 int 存爆成一堆负数排错排到差点把电脑砸了。6.4 我做这类题的一点体会刷 UOJ170 之前我对“数据结构题的复杂度”理解一直停留在“每次操作走多少节点”这个维度上觉得只要一个操作最坏会递归到叶子那就一定超时。做完这题我才意识到数据结构的世界里除了“区间划分”还有“值域压缩”这一层力量很多看似不可做的操作只要你能证明某些值不会反复变化就能把最坏情况卡在可控范围内。这种思路其实不只适用于线段树。处理区间问题时多问自己一句这个操作会不会让某些“状态量”单调递减如果会那么即便它单次代价很贵摊还下来也是可以接受的。这种判断力比记住一两个模板重要得多。最后再分享一个小经验如果打算完整吃透这道题建议你亲手把线段树从头到尾写三遍——第一遍对着题解抄第二遍关掉题解自己写第三遍尝试加入区间取 max 操作扩展。三遍下来你对 pushup 和 pushdown 的理解会完全不同。我现在遇到区间取 min 的裸题基本十分钟内能敲完不出错靠的就是当初那三遍的重复。