第一次见到 SP2713 GSS4 这个题号是在一个收录了大量线段树经典题目的题库里。当时刚把 GSS1 的区间最大子段和、GSS3 的单点修改加最大子段和写熟看到第四题发现操作变成了区间开根号和区间求和瞬间觉得前面那套四个值的合并写法用不上了。后来我才意识到这一题其实是线段树题里一个很典型的“势能修剪”案例。GSS 系列在圈内被叫成线段树八部曲第四题讲的就是这样一件事给一个长度为 n 的非负整数数组m 次操作每次要么把一个区间内的每个数变成它的平方根向下取整要么查询一段区间的和。操作数和数据规模都到了十万级别如果直接按字面意思暴力开根号一个区间套一个区间整体复杂度会直接爆炸但如果你只知道用懒标记写区间加法拿到这题又会无从下手因为开根号这个操作根本没有办法懒标记。解题的关键在于发现一个非常普通的数学生长现象开根号会很快把数压到 1。1. 这道题到底在考什么两个操作之间的不对称性1.1 题面回顾与输入输出约定SP2713 GSS4 的题面非常短核心内容可以压缩成下面几句话。输入包含多组测试数据每组第一行是一个整数 n表示数组长度第二行是 n 个非负整数第三行是操作次数 m。接下来 m 行每行三个整数 op、l、r其中 op 0 表示把区间 [l, r] 内的每个数都替换成它的平方根的整数部分也就是先开根号再向下取整op 1 表示查询区间 [l, r] 的元素和。输出要求每组数据先输出一个 “Case #编号:”然后每个查询单独输出一行相邻两组数据之间还要有一个空行。这里有几个容易在读题阶段就忽略的细节。第一数组元素虽然题目没有把范围写得很夸张但多数实现都要用 long long因为区间和可以轻松超过 int 的范围。第二l 和 r 并不会保证 l 小于等于 r所以代码里要做一次 swap。第三题目没有说只有一组数据scanf 要循环到 EOF。第四0 也需要考虑因为 0 开根号还是 0它同样是一个稳定状态。这些细节看起来琐碎但提交时每一件都可能让你从 Accepted 变成 Wrong Answer。1.2 为什么说 GSS4 和前三题不是同一类题GSS 系列今年头三题GSS1、GSS2、GSS3共同点都是维护区间里某个“无法一眼合并”的信息。讲得稍微细一点GSS1 的经典解法是让线段树每个节点同时维护四个值总和、最大前缀、最大后缀、最大子段和查询时把左右子节点的信息拼起来GSS2 需要处理重复数字只算一次的限制于是用离线的扫描线加线段树把贡献挂到右端点上GSS3 则在 GSS1 的基础上加了单点修改让这四个值在修改后能重新合并。说到底它们还是线段树“区间信息可合并”这一个套路下的变化。题号维护信息核心操作解决思路GSS1总和 / 最大前缀 / 最大后缀 / 最大子段和区间查询线段树四值合并GSS2区间不同数字贡献区间查询离线扫描线GSS3总和 / 最大前缀 / 最大后缀 / 最大子段和单点修改 区间查询动态合并GSS4区间和 / 区间最大值区间开根号 区间求和势能剪枝GSS4 不一样。区间开根号之后你不可能通过左儿子和右儿子的某种合并快速得到父亲的新总和哪怕你维护的再齐全也没法用一个简单的表达式从旧的 sum 推到新的 sum。因此这一题考察的不是信息合并而是“什么时候可以不去更新”。线段树之所以能在 O(log n) 内完成区间加法是因为懒标记可以用“先把影响存起来”的方式推迟应用但开根号这个操作对不同的数产生的变化量完全不同这种不对称性直接封死了懒标记的路。1.3 直接上懒标记为什么会失败我用一个具体例子说明。假设某个节点下面只有两个数16 和 25。这个节点的 sum 是 41。如果对这两个数分别开根号结果变成 4 和 5新区间和是 9。可是如果拿旧的 sum 41 直接开根号得到的是 6.4整数部分是 6和 9 差了十万八千里。再换一个思路给节点挂一个 lazy 标记表示“之后要把这个区间的所有数开根号几次”等查询的时候再统一处理。问题是从最开始的数组状态出发不同位置的数大小差异很大开根号的次数也无法简单合并。一次操作后区间里可能出现一部分数已经变成 1、另一部分数仍然很大没有任何一个节点级的状态能够概括这种中间状态。所以区间开根号这类操作本质上只能逐点处理。可如果每次更新都遍历区间里的每个数字最坏情况下单次操作 O(n)m 次就是 O(nm)十万级别直接超时。于是问题变成了能不能想个办法让“真正需要逐点处理”的次数变得很少这就是下一节要说的开根号收敛性。2. 开根号收敛速度整道题的复杂度根基2.1 从 2^63-1 出发最多六步一个 long long 能表示的最大正整数大约是 9.22e18。没必要真的取那个边界我们看一个同样在 1e18 量级的数比如 10^18。连续向下取整开根号序列是这样走的起始值连续开根号路径10^1810^18 → 10^9 → 31622 → 177 → 13 → 3 → 1约 9.22e189.22e18 → 3.03e9 → 55108 → 234 → 15 → 3 → 1从 10^18 到 1一共只需要 6 次开根号。换成 9.22e18过程也差不多同样是 6 次到达 1。为什么会这么快因为开根号等同于把数值的十进制位数大约减半。一个 19 位数开一次根号变成大约 10 位数再开一次变成 5 位数左右然后再变成 3 位、2 位、1 位。位数减半意味着绝大多数数字很快就会掉到 2 以内。到了 1 之后再开根号结果还是 1到了 0 也同理。所以对一个数组来说每个位置最多经历大约 6 次有效变化之后就永久稳定。这是一个非常强的性质。2.2 “势能”怎么用在线段树上这个性质直接给了我们一个复杂度模型。把每个位置“还需要进行多少次开根号才能到 1”看作这个位置的能量整个数组的总能量一开始最多是 6n。每次真正对一个位置执行开根号它的能量至少减 1。一旦能量变成 0也就是值为 0 或 1后面就再也不会被主动修改。所以整个程序运行过程中所有位置被真正修改的次数之和不会超过 6n。这就是“势能线段树”的由来修改操作的总次数不是由 m 决定而是由初始数组的势能总和决定。在实现上线段树每个节点需要知道一个信息这个区间里还有没有“活跃”的元素也就是有没有仍然大于 1 的数。最简单的方式就是维护区间最大值 mx。如果 mx 1说明这个区间已经整体稳定更新时可以直接返回如果 mx 1说明区间里至少还有一个数需要开根号就必须继续往下走直到把所有活跃叶子都处理掉。一次区间更新可能会访问路径上的许多节点但这些节点都能和某次叶子修改对应起来。每个叶子最多被修改 6 次每次修改要从叶子一路 pushup 回根路径长度 O(log n)。所以总复杂度是 O((6n m) log n)其中 m 次操作每次本身还带 O(log n) 的查找。代入 n 1000006n log n 大约是 1000 万级别加上 m 次操作完全能跑。2.3 为什么说这是均摊而不是严格每次 O(log n)需要注意线段树做区间开根号并不是每一次更新都稳定在 O(log n)。如果一次更新碰到的区间里还有很多活跃叶子它可能会递归到大量叶子节点上单次操作的代价可能远超 log n。比如第一次对整段数组做开根号如果数组里都是 10^18 量级的数这次更新会访问到几乎所有叶子。换句话说单次最坏复杂度没有保证只有总均摊有保证。这和普通区间加法线段树有本质区别。区间加法的懒标记让每次更新严格只走 O(log n) 个节点GSS4 的剪枝条件是“区间稳定”而不是“区间被完全覆盖”所以一次更新完全可能进入很多节点。我们之所以敢这样写是因为每个叶子能承受的有效修改次数有上限头几次更新会消耗大量势能后续更新就会越来越快。理解这一点之后看代码就不会对“最坏情况”产生误判。3. 线段树节点需要维护什么sum 和 mx 的分工3.1 为什么只维护 sum 不够有人可能会想既然每个位置最终都会变成 0 或 1那我用 sum 来判断一个区间是否全部稳定不行吗比如一个区间长度为 3如果 sum 3是不是就说明三个数都是 1这个推理成立的前提是所有数都至少是 1但题目允许 0。考虑一个区间 [0, 2, 1]长度为 3sum 正好也是 3但中间那个 2 仍然需要开根号。如果用 sum len 作为稳定标志这次更新里它会被错误地跳过后续查询区间和的时候2 没有被开根答案自然就错了。更稳妥的判断标准是节点最大值 mx。当 mx 1 时区间内所有元素一定都等于 0 或 1这两种值开根号后都不变因此可以放心返回。维护 mx 的额外代价非常小建树时叶子节点让 mx 等于原值pushup 时 mx max(左子树 mx, 右子树 mx)和 sum 一起更新即可。sum 负责回答区间求和mx 负责决定是否需要继续下钻两者分工明确。有人也尝试过再维护一个 cnt1 表示区间内 1 的个数但那样需要额外考虑很多细节对比下来 mx 是最直接的方案。3.2 update 函数怎么剪枝update 的结构是典型的“两个提前返回”。第一如果当前节点区间和操作区间完全不相交直接返回第二如果 mx[o] 1说明当前区间已经稳定直接返回。只有既不早退、又没到叶子的情况才继续向左右孩子递归。到叶子时用整数开根函数更新 sum[o]同时让 mx[o] sum[o]然后返回。递归回来之后做一次 pushup把左右孩子的 sum 和 mx 合并给父亲。这段逻辑看起来简单但它把两类问题都解决了区间不相交时的访问避免以及区间稳定后的批量跳过。需要特别理解的是即使当前节点区间被操作区间完全包含也不能像区间加法那样直接套用懒标记后返回。完全包含只意味着这个区间内的每一个位置都需要被“考虑”而“考虑”的方式仍然是继续下钻直到遇到 mx 1 的稳定子树或叶子。写代码的时候不要把if (L l r R)这个完全覆盖模型套上来否则要么超时要么逻辑错误。正确模型是一旦某个子区间的 mx 1就说明它的所有后代都再也不会变无论操作区间是否完全覆盖它都可以安全返回。3.3 query 函数与复杂度匹配查询部分就简单多了。标准的线段树区间查询遇到完全覆盖的节点直接返回 sum[o]否则递归左右子树。因为更新函数每次都在叶子修改之后及时 pushup所以每个节点的 sum 始终保持最新查询不需要做任何额外处理。从复杂度看查询严格 O(log n)而更新的均摊复杂度依赖 mx 剪枝两者搭配正好覆盖题目的全部需求。这里也顺便说一个我自己的习惯所有参与区间操作的数据结构我都会把 pushup 单独写成一个函数避免在 build 和 update 里重复写合并逻辑。这题虽然 pushup 只有两行但一旦以后要加别的信息单独函数维护起来会轻松很多。4. 完整代码和提交前检查清单4.1 一份可过的 C 实现下面这份代码是我按自己平时比赛的写法整理的去掉了所有平台相关的东西核心部分可以直接参考。整体思路就是上一节说的 sum mx 双维护更新时用 mx 1 剪枝。#include cstdio #include algorithm #include cmath using namespace std; typedef long long ll; const int MAXN 100005; int n, m; ll a[MAXN]; ll sum[MAXN 2], mx[MAXN 2]; ll int_sqrt(ll x) { ll s (ll)sqrtl((long double)x); while ((s 1) * (s 1) x) s; while (s * s x) --s; return s; } void pushup(int o) { sum[o] sum[o 1] sum[o 1 | 1]; mx[o] max(mx[o 1], mx[o 1 | 1]); } void build(int o, int l, int r) { if (l r) { sum[o] mx[o] a[l]; return; } int mid (l r) 1; build(o 1, l, mid); build(o 1 | 1, mid 1, r); pushup(o); } void update(int o, int l, int r, int L, int R) { if (r L || R l || mx[o] 1) return; if (l r) { sum[o] int_sqrt(sum[o]); mx[o] sum[o]; return; } int mid (l r) 1; update(o 1, l, mid, L, R); update(o 1 | 1, mid 1, r, L, R); pushup(o); } ll query(int o, int l, int r, int L, int R) { if (r L || R l) return 0; if (L l r R) return sum[o]; int mid (l r) 1; return query(o 1, l, mid, L, R) query(o 1 | 1, mid 1, r, L, R); } int main() { int caseNo 0; while (scanf(%d, n) ! EOF) { for (int i 1; i n; i) scanf(%lld, a[i]); build(1, 1, n); scanf(%d, m); if (caseNo) puts(); printf(Case #%d:\n, caseNo); while (m--) { int op, l, r; scanf(%d%d%d, op, l, r); if (l r) swap(l, r); if (op 0) update(1, 1, n, l, r); else printf(%lld\n, query(1, 1, n, l, r)); } } return 0; }这段代码里没有刻意做 memset因为 build 会把当前这组数据用到的所有节点重新赋值一遍。每组数据之间的数组残留不会影响正确性。如果你习惯把数组开成 MAXN 2注意位运算的优先级MAXN 2整体作为数组大小没问题但如果写在表达式中要加括号。这个代码在 n 100000、m 100000 的数据范围内是足够的。4.2 sqrt 与 sqrtl、整数开根的安全写法写整数开根号时最容易犯的错是直接(ll)sqrt(x)然后把浮点结果截断。当 x 很大时sqrt 的 double 精度可能差那么一点点导致结果少 1 或者多 1。比如某些接近完全平方数的巨大整数浮点误差会被放大。更稳妥的做法是用 long double 版本的 sqrtl并且在结果上做两个方向的修正如果 (s1) 的平方还小于等于 x就把 s 加一如果 s 的平方已经大于 x就把 s 减一。这样无论浮点计算往哪个方向偏最后都能回到正确的整数平方根。代码里的 int_sqrt 写了一个很朴素的修正循环。由于题目数组中的值大概在 1e18 以内s 不会超过 1e9所以 (s1) * (s1) 也不会超过 long long 范围这种写法在当前题目下是安全的。如果未来遇到更大范围的数值建议把乘法比较改成除法比较并且单独处理 s 0 的情况避免除零。这个提醒虽然现在用不上但是写通用整数工具函数时值得养成习惯。4.3 多组输入、Case 空行与 l、rr 顺序有三个提交时才看得到的问题必须单独列出来。常见坑原因处理方式只读一组数据题目多组输入while (scanf(...) ! EOF)l 大于 r端点没有保证有序读入后 swap(l, r)Case 之间没有空行输出格式要求每组 Case 前判断是否需要 puts()long long 输入输出用错区间和可能超过 int全程 %lld用 sum len 判断稳定有 0 时可能误判改用 mx 1还有更隐蔽的一点如果直接用sum[o] (ll)(r - l 1)判断区间是否全 1在有 0 的情况下会误判。所以这题统一用mx[o] 1。同时注意整型溢出区间和可能超过 int用 long long 存输出时用 %lld读入时也用 %lld。scanf 和 printf 的组合在这题完全够用不一定要开启流同步。5. 从 GSS4 延伸出去凡是修改次数有限都可以用线段树硬剪5.1 一类“势能线段树”的识别方法GSS4 的意义不只在它本身它展示了一个可以套用到很多题目上的线段树设计模板。这类问题的特征非常明显区间修改不是加、减、乘、赋值这种“能快速作用于整个区间”的线性操作而是对每个元素做一次会改变数值增长速度的变换比如开根号、取模、按位与、求约数个数。这些变换的共同特点是每个元素最多只能被有效修改有限的次数之后就会进入一个稳定状态。一旦发现题目具备这个特征就可以考虑用线段树维护区间“活性”信息通常是最大值在进入某个节点时先判断当前区间还有没有活跃元素。判断“活性”的标准要具体分析不要无脑套 mx。比如区间取模一个数在取模之后可能变小但还没到稳定需要根据模数和当前值判断又比如区间按位与每个数二进制里的 1 只会减少不会增加所以可以用 mx 或者区间内所有元素按位或的值作为活性指标。被修改次数上限越明确势能分析越可靠。5.2 改成询问区间最大值复杂度还成立吗把 GSS4 的查询从区间和改成区间最大值问题会变得更简单。这时线段树每个节点只需要维护 mx无需维护 sum。更新函数的剪枝条件还是mx[o] 1叶子更新后让 mx[o] sqrt(mx[o])查询直接返回区间 max。开根号是单调函数区间最大值更新后就是开根号的最大值所以 pushup 依然可以用 max 合并。整个复杂度分析和 GSS4 完全一样。这个变体值得手推一遍因为它能帮助你理解 sum 在这里只是“附属品”真正驱动剪枝的是 mx。如果一道题查询的是区间和你才需要额外维护 sum如果查询的是最大值那么 mx 一肩挑两职。理解了这一点以后遇到新的势能线段树问题时就知道先确定“用什么指标判断稳定”再确定“用什么信息回答查询”两者不一定相同。5.3 和分块做法对比什么时候用线段树GSS4 用分块也能做每个块维护块内和以及块内最大值更新时如果整块最大值小于等于 1 就跳过整块否则直接暴力遍历块内元素。复杂度大约 O((n m) sqrt(n))在 n 100000 时也可以接受。分块的优势是思路简单不用担心递归和 merge调试方便缺点是如果 n 再扩大一个量级sqrt 部分会成为瓶颈而线段树仍然稳定在接近 O(n log n) 的势能制上。从我个人经验来看这种题目我更倾向用线段树一是因为它能自然处理 n 更大的数据二是势能线段树的思考方式一旦建立迁移到取模、位运算等变体上非常快。第一次写 GSS4 时我按照区间加法的习惯看到完全覆盖就 return结果样例都过不去改成“mx 1 才 return”之后思路一下通透了。后来我再遇到这类操作单调衰减的题第一反应就是找区间最大值做剪枝标志这个习惯就是从这道题养成的。如果让我给一个解题顺序上的建议先证明每个位置只会被修改有限次再确认线段树维护 mx 的代价是 O(1) pushup剩下的事情就是把 update 的提前返回条件写对。返回条件是“到底了”或者“稳定了”不是“完全覆盖了”。