「点缀光辉的第十四分块」。
首先二离没话说。
然后发现这个贡献貌似有点麻烦。
以下复杂度中均视 \(n,m\) 和值域同阶。
设 \(c(x,[l,r])\) 表示 \(x\) 对 \([l,r]\) 的贡献。
那么根据套路需要计算两种贡献：
第一种，形如 \(c(i,[1,i))\)：
即求出 \([1,i)\) 内 \(a_i\) 的倍数 / 约数个数。
前者可以对于 \(j \in [1,i)\)，枚举 \(a_j\) 的约数累加贡献；
后者可以枚举 \(a_i\) 的约数累加出现次数作为贡献。
第二种，形如 \(c(i,[1,x])\ (i \in [l,r])\)：
即求出 \([1,x]\) 内 \(a_i\) 的倍数 / 约数个数。
前者同样是平凡的，考虑同上处理。
但对于后者，考虑到如此询问有 \(O(n \sqrt n)\) 种，则不能沿用以上做法。
考虑对于 \(j \in [1,x]\)，枚举 \(a_j\) 的倍数累加贡献。但这样在 \(a_j\) 较小时是 \(O(n)\) 的。
那么自然而然想到根号分治，设阈值 \(T\)，当 \(a_j > T\) 时直接如此累加贡献。
否则，实际上可以考虑一个这样的方式：枚举一个不超过 \(T\) 的 \(d\) 计算其贡献，具体地，求出 \([1,x]\) 内 \(d\) 的出现次数乘以 \([l,r]\) 内 \(d\) 的倍数的个数。
注意到后者实际上可以用前缀和处理，而前者仍然是平凡的。
这样算下来时间复杂度是 \(O(n\sqrt n + \frac{n^2}T + nT)\)，空间复杂度是 \(O(nT)\)。
看起来 \(T = \sqrt n\) 就行了，但是这题太紧了，导致空间开不下，而线性空间的处理方式会被卡 cache。
于是 \(T\) 取小一点，我块长取 \(799\)，\(T\) 取 \(150\)，然后就直接过去了完全没卡常（
（当时是因为洛谷评测机变快了 lxl 没发现所以没卡我，不过现在也只要不用 vector 预处理每个数的约数，然后带个 O2 就能过了）
另外，一开始全 WA 差点吓死我，拍了一下发现调试信息没删，删了就过了（
代码：
1 |
|