出题人叫我喷，所以我就来喷了。
喷喷喷喷喷喷喷喷喷喷
2021.2 月赛题解
master_rat1 edited 3 年，6 月前
本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。
感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划，使得 EOJ 月赛能够圆满完成。此外，感谢 EOJ 运维团队为月赛提供了重要的技术支持。
最后提前祝各位同学们春节快乐！
A 昔我往矣
只要不是平方级别的算法都能过，比如虚树，树链剖分。
说一个好写的做法。先找出 dfs 序最小和最大者的 lca（也就是 $5$ 个点的 lca），算一下这两点之间的路径长度。然后把其余 $3$ 个点并到这条路径上：在加入一个点 $u$ 时，算一下 $u$ 与前面出现过的点之间 lca 最深是谁，就找到了相较于之前多出来的祖孙链部分，加到答案上去。所以只要求lca就行了。
B 杨柳依依
以每个点为起点做一遍 bfs，记录两两点对之间的最短路径长度和数量，可以通过。
也可以将起点范围缩小至出现过的 $2k$ 个点，常数会小一些。
C 今我来思
给出的条件等价于：$\forall i\in[l,r]，p_i\ge x$ 且至少一个 $i$ 取到等号。对于每个 $i$ 来说，计算包含 $i$ 的所有 $[l,r]$ 对应 $x$ 的最大值，也就是用线段树得到 $p_i$ 的理论下界。如果把这个数列带回询问都有无法满足的，那么显然最终无解。接下来要考虑如何满足“排列”这一限制。
我们从小到大考虑所有的 $i$：它应该被填在排列的哪个位置？首先，一定是在所有满足 $x=i$ 的 $[l,r]$ 交集中（交集为空，则无解）若无 $x=i$ 的询问，则相当于没有限制。其次，一定是某个下界 $\le i$ 的位置（当然是之前没占用掉的），然后直接钦定这两部分交集中任何位置填上 $i$ 即可。
这样填出来的排列一定是符合条件的，具体实现需要一个或两个 set 辅助。（这题方法应该挺多的。）
D 雨雪霏霏
所有格子的海拔自始至终都不变，所以我们一开始建一个 Kruskal 重构树出来。在本题中，可以将所有格子按照海拔从小到大考虑，对于当前格子 $u$ 和周围的某个海拔低于 $u$ 的格子 $v$，将 $u$ 设为 $v$ 所在树的根的父亲。比如样例 $3$ 建出来的树长这样：
在这棵树中，点 $u$ 是点 $v$ 的祖先 $\Longleftrightarrow$ 从 $u$ 出发走四联通、海拔不超过 $L_u$ 可以到 $v$。拓展一下，从 $u$ 出发走四联通、海拔不超过 $L$ 可以走到的点，是 $u$ 的祖先中海拔 $\le L$ 且深度最浅的那个点的子树。找这个点可以用倍增，所以通过 dfs 序，原问题就转化到序列上了（即子任务 $4$）。
序列上计算一段区间内不同颜色数有一个方法：定义 $nxt[i]$ 表示最小的 $j>i$ 满足 $c_j=c_i$，若不存在则设为 $\inf$。那么区间 $[l,r]$ 内不同颜色数就是 $i\in [l,r]$ 且 $nxt[i]>r$ 的个数，可以用树套树解决。用树状数组+动态开点线段树的空间+时间比较稳一点。
跳 $nxt$ 相当于对每种颜色建立的一条链，修改就是在链上做插入和删除，进而修改 $nxt$。所以只要对每种颜色开一个 set 即可。
建出Kruskal重构树后的另一种做法是带修莫队，这里就不展开了，也可以通过本题，实际耗时更小。
Comments
奖项设置等开学后再安排。
抱枕发了喵？
五一后发。如果抱枕不足的话，会发一些别的东西。