势能线段树
维护一个序列的过程中，如果所有的修改操作都只降低势能，即使暴力将区间展开为单点，有效操作的总次数也是有保证的，应为 \(\sum_{i=1}^n \Phi(a_i)\)。
然而，\(\sum_{i=1}^{m}{r_i-l_i+1}\) 却可能达到 \(O(n^2)\) 级别。因此我们需要筛选出当前操作可能会影响到的位置，只对这些位置进行操作。
如果我们可以通过某种区间半群信息 \(w(l,r)\) 快速推断出当前操作是否会对区间 \([l,r]\) 产生影响，就可以使用线段树来维护。这里的线段树称为势能线段树。
具体的，当线段树递归到一个节点 \([l,r]\)：
- 通过区间信息 \(tr[p]\) 推断当前修改操作是否会对 \([l,r]\) 产生影响；若不会，则直接剪枝；
- 递归修改左右儿子；
这样，每一个元素每被进行一次有效的操作，都会产生 \(O(\log n)\) 的时间复杂度。因此总时间复杂度不超过 \(O(\sum_{i=1}^n \Phi(a_i)\log n)\)。
P4145 上帝造题的七分钟 2 / 花神游历各国
题意
你需要维护一个长为 \(n\) 的序列，实现两种操作：
- 给定 \(l,r\)，给区间 \([l,r]\) 内的每个数开平方根（向下取整）；
- 给定 \(l,r\)，求 \([l,r]\) 的区间和；
\(n\le 10^5,\ a_i\le 10^12\)。
注意到开平方根的操作可以使用势能分析。对一个数字 \(a_i\) 开平方根，最多开 \(1+\log \log a_i\) 次，就会把 \(a_i\) 变为 \(1\)，以后的操作就都无效了。
当且仅当一个区间内的所有数字都等于 \(1\)，开根操作对它无效。因此我们可以记录区间 \(\max\) 来判断是否剪枝。
时间复杂度 \(O(n\log n\log \log V)\)。
代码
P9989 [Ynoi Easy Round 2023] TEST_69
题意
你需要维护一个长为 \(n\) 的序列，实现两种操作：
- 给定 \(l,r,x\)，将区间 \([l,r]\) 内的每个数 \(a_i\) 变为 \(\gcd(a_i,x)\)；
- 给定 \(l,r\)，求 \([l,r]\) 的区间和；
\(n\le 2\times 10^5,\ m\le 5\times 10^5,\ 1\le a_i,x\le 10^{18}\)。
一次有效的 \(\gcd\) 至少会让 \(a_i\) 减半。考虑如何判断操作是否会影响当前区间。当且仅当所有数字都是 \(x\) 的因数时，\(a_i\) 不变。此时，区间的 \(\operatorname{lcm}\) 一定也是 \(x\) 的因数。
热知识：\(\operatorname{lcm}_{i\mid x}\{i\}=x\)。
因此我们维护区间 \(\operatorname{lcm}\)。如果 \(\operatorname{lcm}>10^{18}\)，则肯定不是 \(x\) 的因数，直接标记为 INF。这里注意特判。
时间复杂度 \(O(n\log n\log V)\)。