李超线段树 树链剖分 学习笔记

今天学习了李超线段树。

• [洛谷 P4097] 【模板】李超线段树 & [HEOI2013] Segment

  刚开始学李超线段树，觉得挺简单的。其实它跟吉司机线段树有点像，只是维护的东西要少一些，并且代码更好写。

  对于每个节点，考虑维护在它中点处的最高线段编号，那么用类似于吉司机线段树区间取 $\max$：若当前线段完全优于原有线段，那么直接替换；若当前线段完全劣于原有线段，那么直接舍弃；若当前线段与原有线段有交点，那么递归更新当前线段较大的那一段。对于查询，直接把路径上所有的线段取 $\max$ 即可。时间复杂度 $O(n{\log }^{2}n)$

• [洛谷 P4069] [SDOI2016] 游戏

  纯堆码量的题。首先这题一眼树链剖分，一眼李超线段树。这题算是很基础的树剖，只是套的是李超线段树。

  于是 LCA + 树剖 + 李超线段树 就算是码量炸弹了。也许树剖都这样，只是我没怎么写过。所以……先把模板题写了再说。

  • [洛谷 P3384] 【模板】重链剖分/树链剖分

    第一道真正意义上的树剖。之前倒是写过一个有点树剖思想的贪心（但那个好像是长链剖分）。

    一共交了四发，笑点解析：前三发线段树没 pushup。由于当时另外没找到问题，于是我严重怀疑是线段树的问题。然后用那个线段树，写了一个线段树的板子，一测挂了，才发现是没写 pushup，糖丸了。

    第一次写树剖，稍微参考了一下题解代码，但整体还是自己在写。树剖其实挺好理解的。

  写完模板题，该写这道题了。这道题从下午就开始写，一直调到晚上都没调出来，只有明天再补了。