BZOJ 1513 [POI2006]Tet-Tetris 3D


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

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


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

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

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

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

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

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

啊我随便口胡的 T.T

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1513 [POI2006]Tet-Tetris 3D


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,