+++ date = "2021-07-29T18:05:00+08:00" draft = false tags = [] title = "2021 杭电多校 (“中超联赛”) 第四场" authors = ["xry111"] +++

大概过程：

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

License Plate Recognition

题意

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

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

给定一个数组 $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$ 做分类讨论处理，看上去会得到若干个三维偏序问题：

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

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