bzoj 4034: [HAOI2015]树上操作 树链剖分

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4034

 

一眼链剖,但是看到操作3觉得可用LCT,但是没有链剖好写,所以写了链剖

对于操作1:单点修改,就不仔细说了,用区间修改的函数l和r相等就好

对于操作2:每个点记录下dfs时刚进入这个点时的dfs序,再记录下dfs完子树时回到这个点的,修改时区间修改就相当于修改了子树

对于操作3:链剖经典问题,不说了

 

发表评论