题解：CF1732E Location

首先 $\cfrac{\operatorname{lcm}(a,b)}{\gcd(a,b)}=\cfrac{ab}{\gcd^2(a,b)}$。

故当 $\gcd(a,b)$ 一定时，$ab$ 最小会使原式最小。

考虑使用线段树维护。那么对一个结点赋值时，我们就要考虑区间中的 $b$ 与 $x$ 构成最小值。

而 $\gcd(x,b)$ 显然为 $x$ 的因数，考虑枚举 $x$ 的因数 $k$，计算 $\gcd(x,b)=k$ 的结果。

此时统计所有 $k$ 的倍数，取最小的即可。因为此时 $\gcd(x,b)$ 一定是 $k$ 的倍数，而当 $\gcd(x,b)>k$ 时，我们一定会在更大的 $k$ 找到更小的答案。所以这样放宽限制是可以的。

对于 $k$ 的倍数的枚举，不难想到阈值分治。设阈值为 $B$。

当 $n,m,V$ 同阶，取 $B=\mathcal{O}(\sqrt{n }\log n)$，得时间复杂度为 $\mathcal{O}(n\sqrt{n}\log n)$。因为每次修改查询涉及 $\mathcal{O}(\log n)$ 个线段树上的结点。

然而 $B$ 需要开大，空间 $\mathcal{O}(nB)$ 差了点。

不妨对线段树底层分块，设块长为 $K$。那么空间复杂度变为 $\mathcal{O}(\cfrac{nB}{K})$。

如果单次 $\gcd$ 复杂度为 $\mathcal{O}(\log n)$，$\max \{d(n)\}=\mathcal{O}(n^{1/3})$，考虑此时我们的时间复杂度：

总时间复杂度为 $\mathcal{O}((n^{4/3}+nK+\cfrac{nB}{K}+\cfrac{n^2}{B})\log n)$。

取 $B=\mathcal{O}(n^{2/3}),K=\mathcal{O}(n^{1/3})$，总时间复杂度为 $\mathcal{O}(n^{4/3}\log n)$，空间复杂度为 $\mathcal{O}(n^{4/3})$。

当单次 $\gcd$ 做到 $\mathcal{O}(1)$ 时，时间复杂度应该为 $\mathcal{O}(n^{4/3}\log^{2/3} n)$。

较题解区其他人复杂度更优，不过可能有地方没分析到位。