自动搬运

查看原文

来自洛谷，原作者为

	Monomial ?

搬运于2025-08-24 23:07:20，当前版本为作者最后更新于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)$，其实也就是莫队二次离线的基本思路。

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