Acfboy 的博客

感觉是很有意思的一道题，巧妙运用了可并堆来动态维护中位数，还有改严格递增为非严格的 trick, 感觉都挺妙的，不是那么容易想到。

左偏树的基本运用加上一点点的树形 dp。

堆里也可以懒标记。

清新的好题，考验了对树剖的总和理解和运用。

只可惜 赛前四天撞题，这道题没能出现在真正的 CF 里。

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

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

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

题目来源的原文是 2014 ACM-ICPC Asia Mudanjiang Regional Contest, 大概就叫这个名字了。

这题考察了对树直径的性质的理解和运用，有 $\mathcal O(n \log_2 n)$ 的二分做法，但是巧妙运用性质就可以做到线性。

考验对数的直径的 dp 做法变形处理的好题目。

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

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

传送门

模拟赛……一个悲伤的故事，切了俩 ABC 的 F, 结果被这一个绿色的 E 给卡死了，必须写题解记录一下。

传送门

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

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

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

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

一道有趣的构造题。

原有的题解都只讲了构造方法，没有做其它说明，看上去不明不白的，所以搞懂后自己写一篇。讲得比较详细。

提供两种做法，一种是依赖于单调栈和 ST 表的 $\mathcal O(n \lg n)$ 做法，思维难度较低；还有一个绝妙的做法，根本想不到，但不需要任何现成的 算法/数据结构， 时间复杂度 $\mathcal O(n)$。

传送门

这题似乎比前两年的 JOI Final T2 要更有思维难度一些，让我想了比以往长得多的时间，而且开始时觉得不可做，后来调试都没调一下就过了，感觉这题十分有趣，就写题解来记录一下。