简单线段树。

· · 题解

好像没人使用此法过掉此题。

场上想出这个做法，发现复杂度好像是对的。遂写题解。

此方法好想，就是常数有点大。

我们先考虑这个题优一点的暴力怎么做。

那肯定是维护一个数组，然后扫描线扫区间右端点，然后把左边需要修改的 \max 和 \gcd 都改了。

问题是 $\gcd$ 怎么维护。 首先我们发现你这个数组最左边的 $\gcd$ 大概都是 $1$，这些都可以跳过，所以我们考虑在线段树暴力递归的地方加个特判。 如果这一个小区间的 $\gcd$ 的 $\text{lcm}$ 是我们当前右端点的约数，显然此时不需要更新这个 $\gcd$ 了，所以我们维护一个区间的 $\text{lcm}$，暴力修改的时候判断一下是不是新数字的因数，如果是，那就**直接跳过**整个区间，否则，暴力递归俩儿子。 证明如下： 先证明 $\gcd(a,b)\neq b \Leftrightarrow b\nmid a

反证法，假设 \gcd(a,b)= b，则 a=kb\Rightarrow b\mid a。

假设 b\mid a，显然有 a=kb\Rightarrow \gcd(a,b)=b。

所以一个区间扩展后被修改当且仅当 b \nmid a，这个区间可以被跳过当且仅当 b\mid a。

所以一个大的区间可以被跳过当且仅当 \forall i\in[l,r]，x_i\mid a。显然等价于 \text{lcm}_ix_i \mid a。所以我们维护区间 \text{lcm} 就能知道这个区间是否需要被修改了。

注意一个区间的 \text{lcm} 可能很大，我们维护一个 \text{bool} 保存他是不是很大，如果很大，那他肯定不是新加进来数字的因数。

又一次注意到，每个数字每次他的 \gcd 变化的时候会至少变成一半。每次 \gcd 变化的时候最多会造成递归的时候遍历线段树上的 \log n 个节点。共有 n 个数字，所以均摊复杂度就是 \Theta(n\log V\log n) 的。

模板题：https://www.luogu.com.cn/problem/P9989

为什么我又一次发明了别人发明过的东西。