ZOJ 3686 A Simple Tree Problem

被这道题玩得相当惨。。。这道题是一个DFS+线段树的题。

首先这个题是在一棵传统树上面进行大规模的区间读写操作,这是线段树的玩法,但是怎么玩呢?
这个时候DFS就派上用场了,我们通过DFS得到DLR遍历,把dfs时进入一个节点是时间记下来,出去一个节点的时间记下来,就可以得到这个节点的子树在DLR遍历中的区间的开始与结束标号,这样就相当于把2维的树降到一维了。
之后得到了一个一维的数组,就可以开线段树,这里涉及区间更新,还要加开懒惰标记。
这种把树压成线然后再搞是一种很常用很好的姿势!

其实这道题卡死我的就是懒惰标记这里。我原来一直在用zkw线段树,但是因为是自下向上操作没有递归,所以我就根本不知道怎么下手写懒惰标记了,鼓捣2天未果,orz各路大神的适配zkw线段树的懒惰标记是给rmq准备的,不适合这个题,没办法研究递归版本了。

递归版本的话,实现懒惰标记的思路就是:
1.更新时,如果发生了目标区间与当前区间相交的情况,首先把当前节点的懒惰标记下传给下一层,然后再去更新下一层,更新完下一层后,用更新好的下一层更新自身。如果目标区间完全包括当前区间,这个时候就不用往下走了,首先更新自己的值,然后更新自己位置的懒惰标记。
2.查询时,如果目标区间和当前区间相交,这时候需要下传当前节点的懒惰标记,然后进入下一层接着查询,如果目标区间完全包括当前区间,直接更新答案。
3.下传时,我们只操作当前节点的子节点,不可以操作当前节点(否则就重复操作啦),注意我们只下传了一层,所以不仅要操作下面一层的值,还要操作下面一层的懒惰标记,同时清空当前节点的懒惰标记。

1 Comment

  1. […] 懒惰标记的工作原理可以参照:ZOJ 3686 A Simple Tree Problem。 […]

    Reply

Leave a Reply to HDU 1698 Just a Hook | hahaschool Cancel reply

Scroll to top