题意 给定 n 个操作，每次询问求在执行 l∼r 的操作后全局最大值，操作为将 a1 ∼ax 加 y，可为负数。 做法 很容易想到 O(n n logn) 的莫队加线段树做法，理论复杂度只可以过这题的，但是由于线段树的超大常数，直接 T 飞了。原本还想尝试分块代替线段树，可以做到 O(n 47 )，但是感觉这题不会这么简单，没有去试，直接去学正解了，结果写完发现有人写莫队过了，于是又想了一下分块，发现普通分块确实不行，但是分块 plus 好像可行。 分块 plus 就是可以做到 O(n31 ) 修改和查询的分块，线段树1的板题写这个比大部分线段树都快，具体可以看这篇文章，这里我简单讲一下。普通分块是直接讲序列分块，但我们其实可以把每一块再次分块（理论上可以一直分下去，但常数会越来越大），每次更新修改所在小块和大块的贡献，查询直接查大块，假设小块块长为 b，大块块长为 B，则这个分块的复杂度为 O( Bn + bB +b) 取 B=b=n 31 时复杂度最优。 接下来看这道题，注意到前缀加只会改变 x 所在块的最大值位置，其余只要在这个块上打一个 tag，然后查询时从后往前扫累加上每个块的 tag 即可。 设小块块长为 B，大块块长为 B 2 ，则复杂度为 O(nBn + B 2 n 2 )，考虑到除法操作较慢， B 取 2 的幂次时可用位运算代替除法操作，综合考虑 B 取 8 最优。但这样任然无法通过，所以直接循环展开，最终代码跑得飞快，优于大部分正解。 但到这里交上去还是会WA，原因是在处理最后面的散块时会统计到 n 以外的数，如果答案小于 0 就会输出 0 。我们将全局的操作单独拎出来，这样若答案小于 0 ，则我们可以取第 n 个数使得答案为 0 ，最后加上全局的操作即可。 这样我们终于用暴力通过了这题，并且因为正解的超大常数，这种方法是优于大部分正解的。 代码