自动搬运

查看原文

来自洛谷，原作者为

	MeteorFlower God is angry on your doing, and what to bring fire flood.

搬运于2025-08-24 22:52:01，当前版本为作者最后更新于2023-10-26 08:45:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不是，没人写纯正根号吗……退役壬来口胡一下。

看到 $\text{mod}$ 啪的一下就是一个根号分治，很快啊。

考虑模数 $\leq \sqrt V$ 的部分。此时因为模数只有 $O(\sqrt V)$ 种，考虑直接记录每种模数的答案。单次复杂度为 $O(\sqrt V)$ 修改，$O(1)$ 查询。

考虑模数 $> \sqrt V$ 的部分。由于此时商数的级别为 $O(\sqrt V)$，考虑直接存储集合 $S$，询问时枚举商数 $i$，找到集合中最小的 $\geq Y \times i$ 的值然后减一下即可。因此有 $O(n)$ 次修改，$O(n \sqrt V)$ 次查询。使用 $O(\sqrt V)$ 修改，$O(1)$ 查询的值域分块平衡复杂度。具体地，用 $next1_i$ 表示最小的 $\geq i$ 且同块的数，用 $next2_i$ 表示最小的大于第 $i$ 块最后一个数的数。插入新数时修改所属块的前缀 $next1$ 以及前面所有块的 $next2$。查询时先查 $next1$，查不到再查所属块的 $next2$ 即可。

综上所述，总复杂度 $O(n \sqrt V)$。

AFO 了，没时间写代码，应该很简单就不写了。

（吐槽：这种小常数根号题数据范围居然就这么点……生怕乱搞过不去吗……我谔谔。）