CF1422F Boring Queries

题意

询问区间 \(lcm\)，强制在线。

题解

首先考虑每个质因子对于答案的贡献。
对于一个质因子 \(p_i\) 来说其对于区间 \([l,r]\) 的贡献是其最高次幂。
首先考虑离线做法，扫描线，线段树维护答案。
将当前加入的数 \(a_i\) 分解成 \(p_i^{k_i}\)，我们有一个暴力的操作，对于前面所有 \(a_j\) 有 \(p_i\) 的一个一个修改，使得 \([l,i]\) 中所有的 \(p_i\) 的幂贡献都是最大值。

但是这样每次插入做会被叉成 \(O(nlogn)\)，显然没办法通过。

考虑在上述修改过程中的操作，我们从后往前做，记录后缀最大幂。
对于当前修改的点的幂来说，若当前幂数大于后缀最大幂，则消去前面的贡献，然后加入自己的贡献，否则，不加入自己的贡献。
仔细想一想，这其实是一个贡献相消的过程，想一想，实际上就相当于 \(1\) 到最高次幂只做一次贡献，这就有一点像区间数颜色了，我们将一个质数的不同幂看做不同的颜色，这样就可以套用做法了，对于一个幂出现之后对于这个幂上一次出现的位置消去贡献就好了。

对于强制在线，可持久化即可，时间复杂度 \(O(nlogn)\)，空间复杂度 \(O(nlog^2n)\)，code。

另外此题还有对于质因子做根号分治的做法，但比较平凡。