题解 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/
太长不看版：上面的加粗字