+++
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](https://acm.hdu.edu.cn/showproblem.php?pid=6993)

## 题意

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

## 做法

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

# [Didn't I Say to Make My Abilities Average in the Next Life?!](https://acm.hdu.edu.cn/showproblem.php?pid=6989)

## 题意

给定一个数组 $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$ 行)，自闭到最后也没过，赛后才过。