大概过程：

• 开场读 K，然后发现不可做
• 然后读了 F，就是个最小树形图， 但是要求 $10^5$ 点还要输出以每个点为根的答案……
• 然后读了 I，发现事签到题，就去写，结果因为没初始化变量写出了 -O0 能跑一开优化就错的代码。改了以后又因为少写一个特判 WA 了 $114514$ 发。
• 然后帮王老师写了 D 的暴力对拍
• 然后自闭 E 最后没过

License Plate Recognition

题意

给了你一个像素字体，每次输入一个车牌 (保证是我国标准样式，而且没有噪点啥的)，让你输出里面每个字符的 $x$ 坐标范围。

做法

把字全拍扁成一维的，然后除了“川”和“鄂”两个字会断开，剩下都不会。 结果因为没特判“鄂” WA 了 $114514$ 发。

Didn’t I Say to Make My Abilities Average in the Next Life?!

题意

给定一个数组 $a$，每次询问 $x$ 和 $y$，求 $$\sum_{x \leq l \leq r \leq y} \frac{1}{(y-x+2)(y-x+1)}(\max_{l \leq k \leq r} a_k + \min_{l \leq k \leq r} a_k)$$

做法

显然可以拆成最大值和最小值两部分去做，做法是一样的，下面只考虑最大值。

我们考虑 $i$ 位置的这个 $a_i$ 事区间内最大值 (如果有多个相同最大值则必须是第一个) 的情况数，设它左边最近的大于它的位置是 $l_i$，右边最近的小于它的位置是 $r_i$，再假设询问的是开区间 $(x_j, y_j)$ (就给输入都分别加一减一就行了)，情况数就是

$$(i - \max(l_i, x_j))(\min(r_i, y_j) - i)$$

对答案的贡献就是情况数乘以 $a_i$。然后对 $\max$ 和 $\min$ 做分类讨论处理， 看上去会得到若干个三维偏序问题：

• $x_j < i < y_j$
• $l_i \leq x_j$ 或 $x_j < l_i$
• $r_i < y_j$ 或 $y_j < r_i$

然后就现学 cdq 去了，自闭了 $114$ 分钟。 结果到最后一小时突然发现因为 $l_i < i < r_i$ 必然成立，可以把第一个条件合并到后两个条件里面去：

• $l_i \leq x_j < i$ 或 $x_j < l_i$
• $i < y_j \leq r_i$ 或 $r_i < y_j$

就剩下两维了 (就像是 2019 年新生赛接水果那个题一样)， 一维排序一维线段树搞一下就行了。然而由于要打 $4$ 个标记 (分别是区间内应该乘以 $1$, $x_j$, $y_j$, $x_j y_j$ 的项)， 还得分 $4$ 类讨论 (最后写了 $193$ 行)，自闭到最后也没过，赛后才过。