Luogu5309 [Ynoi2011] 初始化

题意：维护一个序列 ，支持下列两种操作。

• 给出 ，将所有模 为 的位置加 。

• 查询区间和，答案对 取模。

，时限 。

---

根号分治经典题。

• 当 时，被修改的位置不超过 个。

可以使用 修改 查询的分块。

• 当 时，考虑对每个不同的 计算贡献。

我们将序列分成大小为 的块，若某一块被 完整包含，贡献显然是 的和。

对于两端的散块，贡献是 的前缀或后缀和。此时 ，暴力维护即可。

总复杂度 。

第二部分常数较大，可以把阈值调小一点。