【VP 记录】EDU078

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-10 14:54:41

记录

只会 ABC，C 还卡了很久。D 题赛后发现是用 set，以后要多练练 map/set。

处理各个字母前缀的出现次数，枚举每个区间作为 $S$ 判断即可。

发现要求就是依次加 $1,2,3\cdots$ 给某个数，最终使两数差为 $k=\left|a-b\right|$

所以先求和直到 $i$ 时 $sum\ge k$，然后分讨：

若 $sum=k$，则答案为 $i$
若 $sum\neq k$，设差值 $x=sum-k$，若 $x$ 为偶数可直接从前面的数中选出 $x$ 的一半放给另一个数，否则需要 $i+1$ 或 $i+2$ 中为奇数的一个来确保奇偶性。

问题可以看成要选 $a$ 数组的一段前缀和 $b$ 数组的一段后缀，发现要两者数量相等，也就是两段中 $1$ 和 $2$ 的数量差互为相反数，因此设 $f_i$ 和 $g_i$ 分别表示两种的数量差为 $i$ 在 $a$ 和 $b$ 中的最大长度。

用前缀和后缀处理 $f_i$ 和 $g_i$，由于数组下标非负，可以加上常量 $n$。最后枚举 $i$ 并计算 $f_i+g_{-i}$ 的最大值，用 $2n$ 减去即为答案。

发现 $i,j$ 两点间有边当且仅当 $l_j<l_i<r_j<r_i$，所以用树状数组可以统计边数，若边数不为 $n-1$ 则一定不是树。

之后用 set 维护所有的线段，每次在 set 上二分，把所有边加进去，最后并查集判断连通即可。

首先发现如果 $x,y$ 两点都与 $u$ 有边相连，则 $x,y$ 之间必定无边，所以需要两点分别在 $l_u$ 和 $r_u$ 或两点的线段有包含关系，因此想到每个点的左边连接所有子树，右边只连接它的父亲。

所以进行树形 dp，每次先递归下去处理完子树的左端点，接着确定根的左端点，最后逆序确定所有子节点的右端点，这样所有子节点是逐个包含的，保证不会有边。