前言

记录点题先...

这届学校体艺节不好说...

[ABC379F] Buildings 2

闲话

C 被坑了，最后 $20 m i n$ 切了本场的 F，避免掉大分...

Solution

很简单，离线后按坐标大小从后往前做，我用了优先队列维护处理 $r$ 之后所有能看到的楼 $p_{i}$ 的高度，并存入树状数组中，接下来只需要求 $l$ 能看得到的楼 $p_{i}$ 的个数，明显 $l$ 要透过 $[l + 1, r]$ 中最高的楼才能看到后面的，那么用线段树维护区间最大值 $M$ ，最后答案其实就是树状数组中的 $[M + 1, N]$ 。

聚会

闲话

LCA都能打错两个细节...

Solution

立刻会想到用 LCA 来做；

接着我就在体艺节演练的操场上捡了几块石头推演，发现三个点两两之间的 LCA 最多只会有 $2$ （至少有 $1$ 个是重复的）；

接着解法就有很多了，可以直接暴力枚举判断所有 LCA 中哪一个点的距离是最优的即可（这一步也可以不暴力枚，用公式求也可以做好像，我不想推了）；

不过为什么最优点一定是在所有 LCA 的其中一个呢？

证明一下，可以发现，最优路径一定不会走重边，否则肯定可以向某个方向移动几个单位的距离从而消除重边。

那最短路径的长度就相当于是三个点两两之间的最短路径的并集的长度嘛！最后就是要找并集中哪一个点使得三个点到其位置都不会走重边，感性理解一下，发现只会出现在三个点之间互相的 LCA 里。

前言 ​

[ABC379F] Buildings 2 ​

闲话 ​

Solution ​

聚会 ​

闲话 ​

Solution ​

前言

[ABC379F] Buildings 2

闲话

Solution

聚会

闲话

Solution