题解 P9989 [Ynoi Easy Round 2023] TEST_69

· · 题解

对正常做法的一个小改进能得到更好的 1log 复杂度。

下面取 V=10^{18}。

考虑维护区间 \text{lcm} 或者“区间 \text{lcm} 已经大于 V”这一信息。修改的时候如果区间 \text{lcm} 大于 V 就暴力递归 pushup，否则如果区间 \text{lcm} 不是 x 的约数才暴力递归，并且 pushup 的时候不需要求左右儿子的 \text{lcm}，而是直接把当前结点的 \text{lcm} 对 x 取 \gcd。

分析复杂度：

容易发现，如果一个结点被暴力递归过至少一次，其 \text{lcm} 一定是 \le V 的。那么此后对这个结点的暴力递归就是对某个数连续取 \gcd 的复杂度。以防有人不知道就说一下，辗转相除的时候递归 O(1) 次能够使被连续取 \gcd 的数减半。而且显然暴力递归的次数是 O(n\log V)，所以这部分的时间复杂度是 O(n\log V)。并且由于线段树链状的递归结构，非暴力递归的部分是一个连续取 \text{lcm} 状物，复杂度和上面类似的，就是 O(\log n+\log V)。

总时间复杂度 O(n\log V+q(\log n+\log V))。实际上并不会更快，代码就不放了。