[BZOJ1513/Luogu3437][POI2006]Tet-Tetris 3D(树套树)

发布于 2018-04-17  160 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1513/Luogu3437][POI2006]Tet-Tetris 3D(树套树)

Description

Tetris 3D "Tetris" 游戏的作者决定做一个新的游戏, 一个三维的版本, 在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止. 作者想改变一下游戏的目的使得它更大众化,在新游戏中你将知道落下的立方体信息以及位置,你的任务就是回答所有立方体落下后最高的方块的高度.所有的立方体在下落过程中都是垂直的并且不会旋转.平板左下角坐标为原点,并且平行于坐标轴.

Tag

树套树

解决思路

观察,题目要求的便是取区间最大值和区间覆盖。那么如果是在序列上的操作,直接用线段树来维护就好了,区间最大值可以直接合并得到,而区间覆盖可以用懒标记来实现。
现在转到了二维平面上,那么就用二维线段树来维护,同样维护懒标记,只不过由于不好下放,采用标记永久化的方式。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1513/Luogu3437][POI2006]Tet-Tetris 3D(树套树)


HNCJ OIer