Acfboy 的博客

封面图是随便找的真实的 Lighting Routing

据说这题有神奇的 LCT 和 树套树 的做法，很可惜，我都不会。

于是搞了一个用欧拉序来维护直径的做法，搭配线段树和倍增 LCA 来解决这题。

其实是这道 线段树分裂 的模板，但是涉及了很多进阶线段树，所以把它称为进阶线段树，包含的操作有动态开点、内存回收、线段树合并、线段树分裂、线段树上二分等。

又是好不容易才 疑似 明白的神仙作业题，考验对懒惰标记的理解，好题目。

此题继续展现线段树的神奇力量——这都能维护！

传送门

传送门

因为 $m$ 非常的小，很容易维护，所以可以按行建立一颗线段树，维护其中联通块的数量。处理联通块的时候用并查集记录上下两个边界的联通状况以及是否有建筑物。

难点在于如何合并，即 pushup。

这不但打了 TM 而且还是世界知名商标，可能受法律保护哦

一道非常惊喜的线段树题。