Luogu5398 [Ynoi2018] GOSICK

第十四分块。

题意： 给出一个长度为 的序列 。

每次询问给出 ，求 ，且 是 （非严格）倍数的二元组 的个数。

（不要求 ， 和 算两个不同的二元组）

允许离线，，时限 ，空限 。

---

我们认为 同阶。

二次离线莫队。

先不考虑 的 的贡献，最后再将答案加上 。

考虑从区间 移动到 ，贡献的变化量为：

可以差分为

我们称这样的询问为二元组 。

将所有询问离线下来，按照 从小到大排序。问题可以转化为维护集合 ，支持

• 加入一个数
• 给出 ，查询

分因数，倍数两部分处理。

• 倍数查询

  维护 表示目前为 的倍数的数的个数。

  插入一个数的复杂度为 ，查询为 ，套用二次离线即可做到 。

• 因数查询

  维护 表示目前为 的因数的数的个数。

  插入数 的复杂度为 。

  考虑根号分治，对于 的数，插入复杂度 ，用二次离线莫队处理。这部分复杂度为 。

  对于剩下 的数，不在莫队中处理（莫队中只保留 的数），分别直接考虑对询问的贡献。

  数 在询问 中的贡献为： 只要知道 与 的区间和即可计算。对于每个 分别处理区间和，然后贡献即可。

  这部分的复杂度也是为 。

一些卡常小技巧：

• 对于数 ，若 则特殊处理，反之用莫队处理。（代替根号分治无脑选 以下的策略）

• 用 std::vector （或者压紧的数组）预处理每个数的约数。无需考虑特殊处理的数。