第十四分块 题解

· · 题解

第十四分块。

这里只讲如何从 [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。

但是当 $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. 指令集优化。 [提交记录](https://www.luogu.com.cn/record/30095095) --- 如果你想**卡空间**，那么需要用到一些技巧。 线性空间（除去 $O(n\log n)$ 存储因数的部分）的做法，我们需要对每个 $x$ 都重新求前缀和数组，并对每个询问计算贡献。由于内存访问非常随机，卡不进 Cache，导致常数无法接受。 所以我们的目标是卡进 Cache。 一个非常 naive 的思路就是，对 $\sqrt n$ 这个阈值再分块，即我们开一个 $n\sqrt[4]n$ 的二维数组，存储连续的 $\sqrt[4]n$ 个数作为因数的信息。这样我们在减小空间的基础上，又尽可能地卡进 Cache。 理论空间复杂度是 $O(n\sqrt[4]n)$。实际上这个阈值没法取太大（因为大于阈值的部分只是一个纯粹的循环，常数非常小，而小于等于阈值的部分则非常吃常数），所以实际使用的空间也比较可观。 [提交记录](https://www.luogu.com.cn/record/30132594)