不知道哪个阴间搬题人，陆续给模拟赛里整了第二分块、第七分块、第十四分块。
第二分块之前写的空间垃圾时间垃圾然后懒得搞了。
第七分块并没有看懂题解。
于是就只能写写这个了。
卡常卡不过别人的主要原因是懒（确信）
Idea：lxl Solution：lxl Std：lxl Data：lxl
“点缀光辉的第十四分块” （妈呀这名字好中二啊（谁叫我要用日本轻小说中的东西命名真是作死））
这题是我研究区间逆序对之后，枚举了一些区间pair贡献的题里面的一个
对这题的评价：8/11
—— lxl 博客
题意简述
给定长为 $n$ 的正整数序列 $\langle a\rangle$，$m$ 次询问给一个区间 $[l, r]$。
查询 $l\le i, j\le r$，且 $a_i$ 是 $a_j$ 的倍数的二元组 $(i, j)$ 的个数。
值域 $[1, W]$，$n, m, W\le 5\times 10^5$。
主要思路
前置知识：莫队二次离线。
然后就只用考虑求 $S([1, i], [1, i])$ 和 $S([1, i], [l, r])$ 力。
下面将以 $n, m, W$ 同阶讨论。
那实际上就两个操作：
- $O(n)$ 次令当前维护区间从 $[1, i - 1]$ 变为 $[1, i]$。
- 求 $S([1, i], [l, r])$，个数为 $O(n)$ 且长度和为 $O(n\sqrt{n})$。
考虑维护 $c(v), b(v)$ 分别表示 $v$ 的倍数/约数的个数。
则加入一个数 $x$，新增的贡献就是 $c(x) + b(x) + 1$。
并且对于每个约数 $y$，$c(y)$ 要加 $1$；每个倍数 $z$，$b(z)$ 要加 $1$。
枚举约数 $O(\sqrt{n})$ 没啥问题。
枚举倍数 $O({n\over x})$ 时间，当 $x$ 太小就退化为 $O(n)$ 了。
于是试图阈值法，设阈值 $D=\sqrt{n}$。
然后 $x>D$ 的就直接枚举倍数，$O(\sqrt{n})$；否则不管。
但是新加一个数的贡献就出问题了。于是维护一个 $cnt(x)$ 记 $x$ 的个数，然后加入数 $x$ 的贡献就是 $1+c(x)+\sum\limits_{d|x}cnt(d)$。
那么考虑第二个操作。
长度和为 $O(n\sqrt{n})$，所以先枚举 $[l, r]$ 的每个元素，假设当前元素值为 $x$。
$x$ 的倍数个数即 $c(x)$，这个已经处理好了；
$x$ 的大于 $D$ 的约数个数即 $b(x)$，这个也已经处理好了；
现在剩下求 $x$ 的不大于 $D$ 的约数个数。
由于 $D=\sqrt{n}$，可以枚举所有不大于 $D$ 的数 $t$，求 $[l, r]$ 中 $t$ 的倍数的数量之和。容易发现这个和就是刚才没求的东西。
$[l, r]$ 中 $t$ 的倍数的数量和可以直接前缀和，维护 $pre(i, t)$ 表示前 $i$ 个数中 $t$ 的倍数的个数。预处理 $O(nD)$。
于是做完了，时间复杂度 $O(n\sqrt{n})$。
卡常
枚举一个数的因数可以 $O(n\log n)$ 空间时间预处理出来扔vector里。
如果直接维护 $pre(i, t)$，空间是 $O(nD)$，意味着 $D$ 大约只能开到 $180$。
然后俺真就直接开了 $180$，然后发现实际上跑得很慢（指勉强过）。
看了看 mrsrz 的代码，发现只开了 $D=99$，一改，果然快了不少（指快了不到 3s）。
反正卡不过 mrsrz 的手写 vector 和「阈值再分块」（其代码做 11 次连续 9 个数作为因数的信息，据说可以卡进 cache）。
参考代码
1 |
|
感觉这题难度主要在莫队二次离线，后面的思路其实非常自然。