题解：CF1732E Location

Eterna · 2025-11-15 14:58:06 · 题解

首先 \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。

• 对于 k \ge B，我们枚举其所有的 \mathcal{O}(V/B) 个倍数，二分一下找区间中有没有这个数，这部分复杂度为 \mathcal{O}(\cfrac{V\log n}{B})。
• 对于 k<B，考虑直接在线段树上维护结果，只需简单预处理即可，共有 \mathcal{O}(nB) 个数。

当 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^{1/3}+\log n)K+B)。向上合并时，复杂度为 \mathcal{O}(\cfrac{nB}{K})。总时间复杂度为 \mathcal{O}(n^{4/3}+\cfrac{nB}{K})。
• 修改：散块部分单次 \mathcal{O}(K \log n)，整块部分单次 \mathcal{O}((n^{1/3}+\cfrac{n}{B})\log n)，分别是小因数和大因数的贡献。共计 \mathcal{O}((nK+\cfrac{n^2}{B}+n^{4/3})\log n)。
• 查询：散块部分单次 \mathcal{O}(K \log n)，整块部分单次 \mathcal{O}(\log n)。时间复杂度为 \mathcal{O}(nK \log n)。

总时间复杂度为 \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)。

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