P5309 [Ynoi2011] 初始化 笔记

操作难以用 log 数据结构维护，所以考虑根号分治，并且可以想到将询问差分，这样就只需要维护前缀和。

对于 $x>\sqrt{n}$ 的，容易想到一个个暴力添加，这一部分是 $m\sqrt{n}$ 次操作，$m$ 次查询，因此需要一种修改 $O(1)$，查询 $O(\sqrt{n})$ 的前缀和维护，使用分块即可。

对于 $x\le \sqrt{n}$ 的，需要注意到题目特殊的数据范围 $y\le x$，这启示 $(y,x)$ 的数量在 $O(n)$ 量级，并且在前缀上，所有 $y+kx$ 构成以 $[1,x]$ 为循环节的周期。因此记 $c_{x,y}$ 表示所有在 $(y,x)$ 上的修改总和，记 $s_{x,y}=\sum _{i=1}^y{c}_{x,i}$，则 $[1,r]$ 的总和可以用 $\lfloor \frac{r}{x}\rfloor s_{x,x}+s_{x,rmodx}$ 表示。这一部分修改 $m$ 次，查询需要对每个 $x$ 都查询，即 $m\sqrt{n}$ 次。因此需要修改 $O(\sqrt{n})$ 查询 $O(1)$ 的方法，又由于 $y\le x\le \sqrt{n}$，所以修改时暴力修改即可。

综上，时间复杂度为 $O((n+m)\sqrt{n})$，空间复杂度 $O(n)$。

注意到 $x\le \sqrt{n}$ 中有大量必要的除、模操作，因此常数远大于 $x>\sqrt{n}$ 的，应适当减小根号分治的阈值。