BZOJ 1513 [POI2006]Tet-Tetris 3D

发布于 2017-12-04  249 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1513

题意:矩形求 max,矩形赋值。


二维线段树即可,本质上就是树套树,内外层线段树分别维护行列。

需要注意的是外层线段树没法 pushup 和 pushdown,复杂度无法接受。所以标记永久化即可。好多题解内层也标记永久化了,其实没有必要。

标记永久化即在修改时路径更新上传标记,找到区间后更新下传标记。

查询时路径上带上下传标记查询,找到区间后用上传标记更新即可。

此题卡空间,需要动态开点,可能是我写的挫,内外层都动态开点了... 跑的很慢...

有些题解直接不动态开点开的三倍空间,实际上是萎的好像? 我记得线段树编号最大会到 4n-3 好像? 

啊我随便口胡的 T.T

 


一个非常弱的准退役OIER