不知道写什么标题

MeteorFlower · 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 了，没时间写代码，应该很简单就不写了。

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