说点闲话。

我打比赛的时候甲流了，特别困和头疼，奥司他韦吃错时间了出了副作用——还恶心，打到 D 题时手已经开始抖了。不过在恶劣的身体条件下以坚强的毅力打过了 ABCDE，本题（F 题）一眼瞪出做法。但在疾病作用下代码实现和调试能力大大削弱，导致最后没能按时 AC，比赛结束 10min 后才过。

本来设想是打到 C 题退赛的。

Prob C

A,B 不讲了，过于水。

注意到题目要求：

\[ \sum_{i\in S} P_i\ge \sum_{i\notin S}W_i \]

的最大 $n-|S|$，两边加上不属于这个集合的部分：

\[ \sum_{i}P_i\ge \sum_{i\notin S} (W_i+P_i) \]

那么这就转化成一个很简单的贪心题了，以 $P_i+W_i$ 为关键字升序排序，然后从小到大取就可以了。

AC 记录。

Prob D

先把 $B$ 排序。

当 $A_i>B_j$，加和加的是 $A_i-B_j$，反之亦然。所以找到第一个 $B_j>A_i$ 的地方，前面的一种处理，后面的另一种处理。假设排序后，满足有位置 $p$，使得 $A_{p-1}\ge B_j$ 但 $A_p<B_j$。那么 $A_i$ 的贡献就是：

\[ \left(pA_i – \sum_{j=1}^{p-1}B_j\right)+\left((m-p)A_i-\sum_{j=p}^m B_j\right) \]

AC 记录。

Prob E

注意到可以用 Trie，因为新序列是在别的序列后面追加元素得到的。

然后做一个 dfs，以结点编号为关键字按顺序 dfs。

AC 记录。

Prob F

来，拆式子！

注意到要求：

\[ \max_{i=l}^r |x-x_i|+|y-y_i| \]

分类讨论！可以看到，有：

• $x+y-x_i-y_i$。
• $x-y-x_i+y_i$。
• $y-x+x_i-y_i$。
• $-x-y+x_i+y_i$。

可以关注到第一个和第四个就是求 $x_i+y_i$ 的最值，第二个和第三个就是求 $x_i-y_i$ 的最值。那么转化为区间最值问题，维护四颗线段树，求 $x_i+y_i$ 和 $x_i-y_i$ 的最值就可以了。

至于正负是无必担心的，这是为什么可以自己思考一下。

AC 记录。