P16829 题解

· · 题解

成功在赛时通过一道 ds 题。

首先把树映射到 dfs 序上，变成区间问题，事实上本题做法和树的关系是滚木。

由于我们要求 LCM，这个数很大，因此我们需要质因数分解后求解。考虑对 LCM 的质因子大小根号分治，令 B=\sqrt {10^5}。

对于不超过 B 的质因子，由于个数很少，为 65 个，因此我们先对 a_i 质因数分解，求出每个质因子出现的次数，修改的时候暴力枚举质因子，相当于区间 checkmin，区间查询 max。线段树维护即可。

对于大于 B 的质因子，由于 B^2>10^5，因此质因子出现次数最多为 1。同时我们发现 a_i 最多会被有效修改一次，然后就变成 1 了。因此可以势能线段树求出每次被修改的 a_i。现在问题就变成：单点修改，区间查询出现过的数的乘积，重复出现不计入贡献。

考虑把贡献放在区间最后一次出现的数上。维护 nxt_i 表示下一个和 a_i 相等的位置。那么 a_i 计入询问 [l,r] 的贡献的充要条件是：i\in[l,r],nxt_i>r，可以看做一个点 (i,nxt_i)。那么把修改拆成加入和删除，就是在平面内加点/删点，查询矩形内数的乘积，CDQ 分治即可。

时间复杂度为 O(q\pi(B)\log n+q\log q\log n)。代码太史，不放了。