有些更新不必变懒

城里有一家只在午夜营业的旅馆。

每个房间门口挂着一个正整数。市政厅每天发布一条奇怪的清洁令：选一段相邻房间，把门牌换成它的整数平方根。

前台还要随时回答某段走廊上的门牌总和。

经理想把清洁令写成一张走廊便签，等客人来问时再统一处理。

便签很快失效。同样的总和，门牌分布可以完全不同；逐个开方以后，新的总和也不同。

前台只记总和，手里没有足够的东西推回每个房间的新门牌。

夜班服务生只好拿着钥匙逐间走。走了几晚，他发现门牌有一个毛病：变小以后，很快就不再变化。

简化题面

┌─ [P4145] 上帝造题的七分钟
├─ 平台: 洛谷
├─ 题意: 支持区间整除平方根更新，并查询区间元素和。
├─ 输入: 初始序列与多次区间操作。
├─ 输出: 每次查询的区间和。
├─ 数据范围: 序列长度与操作次数较大，单次逐元素重算不可接受。
├─ 关键限制: 区间开方无法由区间和直接聚合，稳定元素后续不再变化。
└─ 完整题面: https://www.luogu.com.cn/problem/P4145

便签为什么算不出来

设一段门牌的总和都是 8。分布可以是 [1,7]，也可以是 [4,4]。

逐个取整平方根以后，前者变成 3，后者变成 4。

同一个 sum，对应两个不同的更新结果。整段懒标记没有可计算的聚合值。

线段树只能下钻到更细的区间，直到叶子。听起来像暴力，复杂度却有另一笔账。

门牌会自己耗尽

一个很大的房号会迅速变小：

10^12 -> 10^6 -> 1000 -> 31 -> 5 -> 2 -> 1

房号到 1 以后，后续清洁令都不会改变它。每个元素一生只经历有限次有效更新。

把“还会变化的次数”当作势能。某次区间操作若真的下钻到一个元素，它至少消耗一格势能；势能归零后，整段可以跳过。

单次操作可能访问许多叶子，长时间累计的总下钻次数仍受所有元素势能总和控制。

这就是摊还分析给出的通行证。代码逐元素做事，证明负责说明它不会永远做下去。

旅馆需要一个哨兵

当前实现用区间和判断一段走廊是否全是 1：

if (tree[p] == r - l + 1) return;

题目保证所有门牌为正数。长度为 len 的区间，和等于 len 时，每个门牌都只能是 1。

这个哨兵依赖正数条件。若允许 0，[0,2] 的和同样等于长度，便签会错误跳过一次仍然有效的开方。

更通用的实现可以维护区间最大值，判断 max <= 1。

什么时候该放弃懒标记

先检查整段更新能否只靠节点摘要完成。能算出新摘要，懒标记才有地方落脚。

算不出时，再看每个元素会不会快速稳定。稳定次数有限，逐点下钻仍可能通过势能分析获得可接受的总复杂度。

这两件事是两条不同的路：一条靠延期，一条靠变化次数耗尽。

午夜清洁结束。前台打印出走廊总和，服务生把钥匙放回墙上。

经理最后才承认，便签省下的是脚步，门牌耗尽的是时间。

发布信息草案

• 标题：有些更新不必变懒
• 摘要：区间开方无法从区间和聚合，但元素变化次数有限，逐点下钻可由势能分析支撑。
• 标签：线段树、区间开方、势能分析、摊还复杂度、懒标记