题解 P3437 【[POI2006]TET-Tetris 3D】

【POI补全计划#21 POI2006 TET】 无智商选手oscar又来写题解啦！ 这道题看起来像是一个裸的二维线段树，然而写到一半发现二维线段树上发不了lazy 于是我去请教了h*****5巨神，他说可以用四叉树做，就是不知道O(nq)能不能跑过，于是我就写了一棵四叉树！ 代码：<http://paste.ubuntu.com/25659343/> 然而TLE了... 于是我又去请教o********d巨神，他说可以标记永久化.... 故事部分完了，我们来分析一下这个“标记永久化”是个啥 画外音：就是不发lazy（ 那么**整体思路就是建一棵树套树，外层节点的lazy和maxx信息用一棵内层树维护，这样就可以正常地修改和查询了。。** **修改时更新路径上所有节点的maxx信息，更新最下层节点的lazy信息** **查询时用路径上所有节点的lazy信息和最下层节点的maxx信息来更新答案** **正确性请读者自己思考（逃）** 于是我们又写了一课指针版的树套树，代码：<http://paste.ubuntu.com/25659399/> 然而MLE了... 于是我就去请教了o***r蒟蒻，决定去掉节点内部的l和r信息，因为访问到节点的时候一定是从上层节点下来的，所以l和r可以通过父节点计算出来 代码：<http://paste.ubuntu.com/25659376/> 然而还是MLE... 于是我又去请教了o***r蒟蒻，决定改为**堆式存储**，于是就愉快地AC了！ （貌似多开了一个毫无用处的数组） 最终AC代码：<http://paste.ubuntu.com/25659418/> **太长不看版：上面的加粗字**