P5309 [Ynoi2011] 初始化 题解

看到 Ynoi 题，就要想到根号算法 + 卡常。这什么毒瘤卡常题（）

显然对序列分块，这样可以维护查询，但是怎么修改呢？

考虑到修改操作的步长为 \(x\)，那么设一个阈值 \(p\)，对于 \(x \geq p\) 暴力跳暴力修改，对于 \(x < p\) 另外想办法，实际上就是一个根号分治思想。

发现题目保证 \(y \leq x\)，于是我们可以假想以 \(x\) 为周期进行序列分块，然后发现我们只需要维护这个块的第一个块的信息，就可以推知整个序列的信息，因为这玩意有周期性。

然后对于查询 \([l,r]\) 而言，首先查原始数据（含暴力修改）需要 \(O(Size)\) 的时间，而枚举周期又需要 \(O(p)\) 的时间，这意味着我们需要 \(O(1)\) 查询每个周期对询问区间的贡献，这个维护一下前后缀和就可以了。

最后我卡常的时候是将块长调到 300 左右，阈值调到 200，然后卡过去了（）

卡不过去的可以调下块长和根号分治的阈值。

Code：GitHub CodeBase-of-Plozia P5309 [Ynoi2011] 初始化.cpp