2404 杂题记录

1. 线段树维护 gcd

查线段树势能提到的一个例题。线段树势能里面强调线段树维护区间 gcd 的时间复杂度 为 遍历数组的复杂度 + 总 gcd 的时间复杂度，即 O(n + log C)，均摊到每一个操作上就是 O(1 + log C / n) = O(1)，所以我们可以 O(nlogn) 解决线段树维护区间 gcd。

不过网上做法好像和我想象的不一样（？）考虑由 gcd(a,b)=gcd(b-a,a) 得到 gcd(a,b,c) = gcd(gcd(a,b-a),gcd(b,c-b)) = gcd(a,b-a,c-b)。所以 gcd(a[l]...a[r])=gcd(a[l],gcd(b[l+1]...b[r]))，其中 b 是 a 的差分数组。维护 b，可以 logn 得到 a[l]，logn 得到 gcd(b[l+1]...b[r])，区间修改转单点修改了。

题外，如果不带区间修改，可以 st 表维护，logn 回答。题解

2. 势能线段树

口胡一下这个东西，也是在某题解看到了一眼就学了。学的挺一头雾水的。
这个东西实际应用其实就是在某些操作下，区间内的元素会在某些形式上趋于一样。比如区间取 min/max、区间开根、区间删除 >= p 的数等等。博客

重点我们要考虑一下它的证明。套路大概是：我们定义一个势能，观察这个势能的 变化次数上限 和 它单次变化带来的复杂度 的关系，然后利用全局的势能总和 去分析时间复杂度。
势能分析复杂度的帮助还是很大的，比如 这 些 。

以区间开根这个比较显然的例子举例，我们维护一下区间最大值和最小值，每次区间修改的时候，在 L<=l,r<=R 的时候我们不退出，而是判断 minmax 是否趋同，若是，区间 tag 变化；反之，递归下去。复杂度均摊不大，可能单 log 或双 log。区间去 maxmin 是单 log 的。区间开根例题 | 区间开根势能线段树

复杂度分析有点凌乱，唯一的启发可能是，对一些数值方面的操作，我们可以维护一下上下界，保证“在 L<=l,r<=R 时暴力递归下去处理的复杂度不高”。