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

2017-10-02 15:50:16


【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/

太长不看版:上面的加粗字