给定长为 $n$ 的数列,$m$ 次操作涉及单点修改和区间最大值。
HDU 1754

题解

线段树的裸题,这里测试分块用。
分 $\sqrt{n}$ 个块,维护每个块代表的区间的最大值。
查询时,对区间两端的不完整块暴力统计,再用中间的完整块维护的信息更新最大值。
更新时,只需遍历当前块中的所有元素维护当前块的最大值。
注意到,当前块的最大值在修改后会成为待修改位置以外的其他位置的值,仅当修改前当前块的最大值等于待修改位置原来的值,且修改后该位置的值变小。因此,一个优化是仅在这种情况下遍历当前块中元素,其他情况下只需用修改到的值更新当前块的最大值。

代码

hdu1754_blocks.cpp
(辣鸡 HDOJ 挂掉了,这段代码并没有提交。。)