题解：P11443 [Code+#6] 校门外的树

Monomial · 2024-12-29 21:01:44 · 题解

显然有一个莫队的思路，我们维护 cnt_{i,j} 表示所有有 i^{k} 作为因子的 i^{j} 贡献的次数，这个很显然可以 \mathcal{O}(\log V) 维护，每次莫队更新时加上或除掉就行，那么我们有了一个 \mathcal{O}(n \sqrt{n} d \log V) 的做法，其中 d 表示最大不同质因子数。

这个莫队做法很不优，因为更新复杂度达到了 \log 级别。我们去考虑一次更新操作的本质，以右移右端点为例，其实就是计算 [l,r] 对 r+1 位置的贡献，我们设这个为 f(r+1,[l,r])，它显然可以拆分为 f(r+1,[1,r])-f(r+1,[1,l-1]) 的形式。依照前面的方法枚举前缀，维护 cnt，每次去计算 f 的贡献，时间复杂度 \mathcal{O}(nd\log V+n\sqrt{n}d)，空间复杂度 \mathcal{O}(n \sqrt{n})，足以通过。

接下来可以进一步优化这个做法，我们发现一次连续的更新其一部分前缀的端点是固定的，那么直接记下位置的区间即可，对于另一种情况很容易发现是 f(x,[1,x-1]) 的形式，预处理即可，空间复杂度 \mathcal{O}(n)，其实也就是莫队二次离线的基本思路。

注意，本做法需要卡常，比如使用光速幂。