CodeChef Chef and Churus 题解

对给出的 \(n\) 个区间分块，设块长为 \(B\)。

每个块内计算每个位置的贡献（被覆盖次数）。具体地，记 \(f_{i,j}\) 表示第 \(i\) 个块第 \(j\) 个数被覆盖了多少次，这个可以用差分轻松维护。预处理复杂度 \(O(\frac{n^2}{B})\)。

现在考虑修改。记 \(ans_i\) 表示块 \(i\) 的贡献，那么对于每个块 \(i\)，\(ans_i\leftarrow ans_i-f_{i,x}\times a_x+f_{i,x}\times y\) 即可。对每个块处理完后再令 \(a_x=y\)。时间复杂度 \(O(\frac{mn}{B})\)。

最后是查询。整块直接累加 \(ans\) 值即可，问题是散块。一个 naive 的想法是对每一块维护一个线段树/树状数组 ，然后对 \(2B\) 个区间都求一下区间和。但是这样复杂度会带 \(\log\)，不是很优。

考虑对原序列再分一次块，但是发现如果每个位置维护当前 \(a_i\) 的值的话复杂度会凭空多一个 \(B\)，显然不行。转换思路，第 \(i\) 个位置维护 \(\sum_{j=1}^{i}a_j\)，也就是前缀和。那么单点修改就对应了 \([x,n]\) 这一个区间的修改，复杂度 \(O(B+\frac{n}{B})\)，查询就直接 \(O(1)\) 差分即可。这样散块的复杂度就变成了 \(O(\frac{n}{B}+B)\)。

现在重新分析一下复杂度：预处理复杂度不变。而区间和原序列的分块互不影响，所以修改的复杂度为 \(O(\frac{mn}{B}+B+\frac{n}{B})\)，查询复杂度 \(O(\frac{n}{B}+B)\)。此时 \(B\) 取 \(\sqrt{n}\) 最优，为 \(O(n\sqrt{n})\)（\(n,m\) 同级），实现了复杂度平衡。

代码：

咕咕咕。