自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:10:22，当前版本为作者最后更新于2020-02-04 20:33:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第十四分块。

这里只讲如何从 $[1,i]$ 递推到 $[1,i+1]$，关于二次离线莫队的具体写法请参见第十四分块(前体)的题解。

考虑用 $b_i$ 表示 $i$ 的因数的出现次数，$c_i$ 表示 $i$ 的倍数的出现次数。那么一个数 $x$ 当前的贡献就为 $b_x+c_x$。

考虑新加入 $x$ 这个数，所有 $x$ 的因数 $y$ 对应的 $c_y$ 就要加 $1$，所有 $x$ 的倍数 $z$ 对应的 $b_z$ 也要加 $1$。

$5\times 10^5$ 内的数的因数个数不多，单次枚举因数部分的复杂度可以看做 $O(\sqrt n)$。

但是当 $x$ 比较小的时候，枚举 $x$ 的倍数就是 $O(n)$ 的。

考虑根号分治，对 $x>\sqrt n$ 的部分直接暴力枚举，单次复杂度 $O(\sqrt n)$，对于 $x\leq \sqrt n$ 的部分，使用另外的方法。

对于 $x\leq\sqrt n$ 的部分，我们考虑解决二次离线莫队中两个需要维护的东西的计算。

• 计算 $[1,i-1]$ 对 $i$ 的贡献，即计算 $a_ i$ 的倍数在 $[1,i-1]$ 中的出现次数。

  $a_j$ 是 $a_i$（$j\lt i$）的倍数，相当于 $a_i$ 是 $a_j$ 的因数，所以我们对每个数统计它作为因数的出现次数即可。

• 计算 $[1,i]$ 对 $[l,r]$ 的贡献。我们还是要解决询问单点的倍数/因数个数的问题。但这里总询问次数为 $O (n\sqrt n)$，所以我们必须 $O(1)$ 查询。

  现在的问题在于，我们无法统计 $x$ 的因数中，小于等于 $\sqrt n$ 的因数的出现次数。对于大于等于 $\sqrt n$ 的因数，直接枚举其倍数并加上贡献的复杂度是正确的，但小于等于时是不正确的。

  我们反过来考虑。我们对每个因数 $x$，如果知道了 $l,r$ 内 $x$ 的倍数的出现次数，那么这个 $x$ 作为因数的贡献就得到了。我们对每个 $\leq \sqrt n$ 的因数 $x$ 都计算贡献即可。

  考虑如何快速计算区间 $[l,r]$ 内 $x$ 的倍数的出现次数。我们对每个 $x$，记录 $pre_{x,i}$ 表示前 $i$ 个数中，$x$ 的倍数的出现次数。然后在计算 $[1,i]$ 对 $[l,r]$ 的贡献的时候，我们记录 $[1,i]$ 中每个数的出现次数，然后 $pre_{x,r}-pre_{x,l-1}$ 乘上 $x$ 在 $[1,i]$ 的出现次数，就是 $[l,r]$ 中的数作为倍数，$[1,i]$ 中的数作为因数（不超过 $\sqrt n$） 时的贡献。

这样各部分维护的复杂度都为 $O(n\sqrt n)$ 或 $O(m\sqrt n)$。

时间复杂度 $O((n+m)\sqrt n)$。

关于空间复杂度，直接对 $O(\sqrt n)$ 个因数开前缀和数组存是 $O(n\sqrt n)$ 的。可以只用一个前缀和数组，对每个因数分别重新计算，可以做到 $O(n)$。

卡常数部分：

1. 线性空间的做法会被卡 Cache，所以要写空间 $O(n\sqrt n)$ 的做法。由于空间限制，根号分治的阈值只能开到 $100\sim 200$。
2. 每次都 $O(\sqrt n)$ 计算一个数的因数效率非常低，可以开 vector 存每个数的因数，一开始预处理每个数的因数，然后就可以直接遍历 vector。时空复杂度 $O(n\log n)$。
3. 存储二次离线的询问时，STL 的 vector 较慢，需要手动分配连续内存。
4. IO 优化。
5. 指令集优化。

提交记录

如果你想卡空间，那么需要用到一些技巧。

线性空间（除去 $O(n\log n)$ 存储因数的部分）的做法，我们需要对每个 $x$ 都重新求前缀和数组，并对每个询问计算贡献。由于内存访问非常随机，卡不进 Cache，导致常数无法接受。

所以我们的目标是卡进 Cache。

一个非常 naive 的思路就是，对 $\sqrt n$ 这个阈值再分块，即我们开一个 $n\sqrt[4]n$ 的二维数组，存储连续的 $\sqrt[4]n$ 个数作为因数的信息。这样我们在减小空间的基础上，又尽可能地卡进 Cache。

理论空间复杂度是 $O(n\sqrt[4]n)$。实际上这个阈值没法取太大（因为大于阈值的部分只是一个纯粹的循环，常数非常小，而小于等于阈值的部分则非常吃常数），所以实际使用的空间也比较可观。

提交记录