【题解】P10538 [APIO2024] 星际列车

5ab_juruo · 2024-06-16 09:31:46 · 题解

复读一下官方 sol 的 1log 做法。

令 f_i 表示，转移到第 i 条边，且考虑了所有 A_i 之前的餐食的最小费用。则显然有如下转移：

按照 A_i 升序转移，可以做到平方的复杂度。若要优化，注意到如下性质：

• 对于 i,j 和时刻 c，若 B_i\le B_j，且 f_i+cost(B_i+1,c)\ge f_j+cost(B_j+1,c)，则对于所有 A_i>c 的转移，都是 j 比 i 更优秀。

考虑对每个节点维护一个单调队列状物，将 Y_i 相同的 i 按照 B_i 升序存入链表中，且对于当前时间 c 满足 f_i+cost(B_i+1,c) 递增。若在某一时刻，链表中相邻的 i,j 出现了顺序反转，则将 i 从链表中删除即可。

考虑相邻元素 i,j 何时发生顺序反转，即在 [B_i+1,B_j] 间插入了至少 \lceil (f_j-f_i)/T_{Y_i}\rceil 次餐食，用主席树维护区间第 k 大即可。

将所有事件按照时间升序处理，用小根堆维护，总复杂度 \mathcal{O}(n\log n)（视 N,M,W 同阶）。

代码：https://qoj.ac/submission/445704