# Segment Tree Beats 与势能剪枝 ## 本节目标 理解区间非线性修改为何通常不能直接 Lazy，掌握 Beats 的“最大值、严格次大值、最大值个数”条件更新，并能用势能证明取模、约数替换等递归到叶的操作总复杂度。 ## 前置知识与课前自测 前置：Lazy Segment Tree、摊还分析。 1. 对区间做 `a_i=min(a_i,x)`，只保存最大值和区间和够吗？ 2. 若 $secondMax答案 1. 不够，还需知道最大值有几个以及其余元素的最大值。 2. 只有等于最大值的元素，且它们统一变成 x。 3. `max ## 问题动机与核心知识 普通 Lazy 要求修改能由节点摘要直接更新，并可安全传给孩子。`chmin(x)` 在 $secondMaxHint 1节点保存 `max1,max2,countMax,sum`。
Hint 2整段覆盖且 `max2 < x < max1` 时可只降低最大值组。
### Observations - 修改只区分“大于 x”和“不大于 x”；节点中若大于 x 的只有最大值一档，就能整体处理。 - 直接条件必须是严格 `max2Hint 1节点保存最大值与和；若 `max < mod`，整段不变。
Hint 2其余情况递归到叶做 `%`，再回拉。
### Observations - 取模无法仅凭 sum/max 直接算新和，但 max 能证明整段稳定。 - 若 $x\le a$ 且发生 `a%=x`，新值严格小于 $a/2$；包括 $x>a/2$ 时余数为 $a-xHint 1$D(1)=1,D(2)=2$，值不超过 2 后永久稳定。
Hint 2节点最大值不超过 2 时整段跳过。
### Observations - 约数函数不单调到“每次减半”，但 $10^6$ 范围内迭代极快进入 2。 - 可先筛法预处理所有 $D(x)$，叶修改 $O(1)$。 - 最大值是稳定性证书；区间和用于回答查询。 ### Editorial 与正确性证明 筛法为每个约数 $d$ 给倍数加一，得到 `divisor_count`。替换操作在 `maximum<=2` 的节点停止，否则递归到叶替换。被跳过段所有元素确为不动点；未跳过段最终访问每个尚不稳定叶并精确更新。每点有效变化次数为很小的 $O(\log\log A)$，总访问均摊可控。 ### 核心伪代码与附件 ```text precompute D[x] for x <= 1e6 by divisor sieve replace(node): if node.maximum <= 2: return if leaf: value = D[value]; return recurse; pull sum and maximum ``` [完整 C++17 附件](../../参考实现/08-高级线段树与树状数组/CodeForces-920F.cpp) ## 灵活性训练 [CodeForces-679E Bear and Bad Powers of 42](https://vjudge.net/problem/CodeForces-679E)（3100）维护区间加/赋值，并反复避开坏值 $42^k$。它要求节点保存到下一个坏值的最小距离，在触碰阈值时局部修复；用于训练“维护下一次结构变化的时间”，不作后续前置。 ## 扩展与联系 Beats 不是任意非线性修改的万能模板。能否使用取决于：节点是否能识别少数受影响值档、直接更新后摘要是否闭合、失败下沉是否有势能保证。 ## 总结与自检 1. `max2