做题记录 25.10.11

szt100309 · 2025-10-11 13:42:00 · 个人记录

\purple\odot P7219 [JOISC 2020] 星座 3

从下往上扫描，用并查集维护极大不存在船的连续段

考虑反悔贪心，建立一棵树状数组，i 位置保存在 x=i 处放置一个星星，为了消除矛盾而需要的代价

扫描到 y=i 时，枚举星星 (j,c)，令 cs 为放置在 j 的代价，若 c\le cs 则消除当前的更优，令答案加上 c，否则消除之前的更优，答案加上 cs，并令树状数组上 j 所在连续段对应的区间整体加上 c-cs，表示反悔的代价

时间复杂度 O(n\alpha(n)+m\log n)

代码

参考

QOJ #3869. Gastronomic Event

对于一种排列方式 a_{1\sim n}，对于任意一条边 u,v，若 a_u<a_v 则定向 u\to v，否则定向 u\gets v，显然一种 a 唯一确定一种定向，一种定向至少对应一种 a，而一种定向对应答案为有向路径数量

转化为选择一种定向方式使得答案最大

用 a\to b 表示存在有向边 a\to b，用 a\dashrightarrow b 表示存在 a 到 b 的有向路径，反方向同理

定理 1：对于 a,b,c,d 满足 a\to b\dashleftarrow c\to d，调整为 a\gets b\dashleftarrow c\to d 并翻转子树 a 内（此处子树指以 a-b-c-d 链为根时的子树，下同）边的方向，或调整为 a\to b\dashleftarrow c\gets d 并翻转子树 d 内边的方向，两种操作中至少一种使答案增加

证明：

• 令 A 为 初始时 以 a 结尾的有向路径数量（显然起点在子树 a 内）
• 令 B_{out} 表示以 b 为起点的有向路径数量（显然终点在子树 b 内）
• 令 B_{in} 表示以 b 为终点的有向路径数量（路径不经过 a\to b）
• 显然上述操作不改变子树内部路径合法情况（要么不变，要么整体逆序，都不改变是否为有向路径）
• 若对 a\to b 操作，则原本的 u\dashrightarrow a\to b\dashrightarrow v 不再计入答案，而 u\dashleftarrow a\gets b\dashleftarrow w 计入答案，其中 u,v,w 分别在 A,B_{out},B_{in} 对应集合中，答案增量为 \Delta_1=A(B_{in}-B_{out})
• 同理对 c\to d 操作增量为 \Delta_2=D(C_{out}-C_{in})
• 因为所有以 c 为终点的路径后都可接上 b\dashleftarrow c 从而变为以 b 为终点，因此 B_{in}\ge C_{in}+1，同理 C_{out}\ge B_{out}+1
• 因此 (B_{in}-B_{out})+(C_{out}-C_{in})\ge 2，即 B_{in}-B_{out} 和 C_{out}-C_{in} 至少一个 \ge 1，从而 \Delta_1 和 \Delta_2 中至少一个 \ge 1，选择正的那个显然答案增加

由定理 1 可得：任意一条路径都可调整为至多改变方向一次且答案不劣（显然答案有限，因此一定存在最优状态使得所有路径都至多改变一次方向）

定理 2：最优解中存在点 u，使得以 u 为根时，u 的所有子树内的点定向相同（其中一个点的定向为它和它父亲之间边的定向，向上或向下）

证明：

• 任意选择一个点 u，定义一个点 v\ne u 不合法当且仅当存在 v 的儿子 w 使得路径 u-w 在 u 处改变方向
• 若对于当前 u 不存在不合法点，则已经满足题目的条件
• 否则所有不合法点必然在 u 的同一子树中（不然选择两个不在同一子树中的不合法点，显然它们相应的儿子之间的路径至少改变两次方向）
• 对于不合法点 v，设它所在 u 的子树的根为 r，即 r 为 u 的儿子且 v 在子树 r 中，则 (u,r) 的定向与 u 同其它儿子之间的边的定向不同，否则显然存在至少改变两次方向的路径
• 此时令 r 为根，显然不合法点的数量严格减少
• 经过若干次调整后，必然能够使不合法点数量变为 0

考虑枚举点 u，设它的子树大小为 sz_{1\sim k}，每个子树内部贡献为子树内点深度之和（深度定义为到 u 的距离），与定向无关，容易换根 dp 求出

设定向为指向根的子树大小总和为 s，则剩余部分贡献为 (s+1)(n-s)

当 u 不是重心时，一定存在一个子树大小 >\frac n2，取该子树为 s 最优

当 u 为重心时，这样的 u 至多两个，对应的 sz 至多 O(\sqrt n) 种，二进制分组后至多 O(\sqrt n) 个值，用 bitset 求出所有合法的 s，时间复杂度 O(\frac{n\sqrt n}\omega)

定理 3：存在最优解使得选择的 u 为重心

证明：

• 假设选择的点为 u，它 >\frac n2 的儿子为 t，令 d_x 为 \min(\text{dis}(x,u),\text{dis}(x,t))，则答案为 \sum d_x+sz_t+(sz_t+1)(n-sz_t)
• 若翻转边 (u,t)，则答案变为 \sum d_x+(n-sz_t)+(n-sz_t+1)sz_t
• 而 (\sum d_x+(n-sz_t)+(n-sz_t+1)sz_t)-(\sum d_x+sz_t+(sz_t+1)(n-sz_t))=0，答案不变
• 因此令 t 为新选择的点
• 显然反复进行以上操作最终 u 为重心
• 显然通过该过程可知存在两个重心时选择任意一个答案相同

因此实际上只需要选择任意一个重心，按之前的算法求出答案即可

总时间复杂度 O(\frac{n\sqrt n}\omega+n)

代码

参考