给定长为 $n$ 的数列,$m$ 次操作涉及区间加和区间最大值。
$n, m \leq 10^5$。
洛谷 3372

题解

同样是测试分块用了。
分 $\sqrt{n}$ 个块,维护每个块代表的区间的和。
区间更新时,两端的不完整块可以暴力更新,但对于中间的完整块,我们不能仅仅更新它们记录的区间和,因为查询操作需要用到原数组的值,而原数组的值在区间加后会变化。暴力更新原数组是 $O(n)$ 的,难以直接维护原数组。
类似于线段树的区间操作,我们可以在更新过程中对每个块维护块中所有位置被同时加上的量,从而块 $i$ 实际的和等于 $sum(i) + tag(i) \times block\_size$,查询过程亦容易实现。

代码

luogu3372_blocks.cpp
跑得比线段树慢一倍。