企业官网建设流程全解析

第一次见到 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 的基础上加了单点修改，让这四个值在修改后能重新合并。说到底，它们还是线段树“区间信息可合并”这一个套路下的变化。

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^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 = 100000，6n 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]，长度为 3，sum 正好也是 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，并且在结果上做两个方向的修正：如果 (s+1) 的平方还小于等于 x，就把 s 加一；如果 s 的平方已经大于 x，就把 s 减一。这样无论浮点计算往哪个方向偏，最后都能回到正确的整数平方根。

代码里的 int_sqrt 写了一个很朴素的修正循环。由于题目数组中的值大概在 1e18 以内，s 不会超过 1e9，所以 (s+1) * (s+1) 也不会超过 long long 范围，这种写法在当前题目下是安全的。如果未来遇到更大范围的数值，建议把乘法比较改成除法比较，并且单独处理 s = 0 的情况，避免除零。这个提醒虽然现在用不上，但是写通用整数工具函数时值得养成习惯。

4.3 多组输入、Case 空行与 l、rr 顺序

有三个提交时才看得到的问题，必须单独列出来。

还有更隐蔽的一点：如果直接用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 的提前返回条件写对。返回条件是“到底了”或者“稳定了”，不是“完全覆盖了”。