p10538 sol

AllenJYL · 2025-01-10 20:41:50 · 题解

我的二分队列决策单调性启蒙题。设 N,M,W 同阶。

拿一个 dp 算答案。设计 dp 状态 f_i 表示经过第 i 条边，当前时刻是 B_i 的答案。按照 A_i 从小到大转移。容易列出转移式

其中 Cost_{l,r} 表示左端点大于等于 l，右端点小于等于 r 的饭的数量。这可以拿主席树搞掉。

预处理 Cost 时间复杂度 O(N^2)，主席树是 O(N^2\log N)。前者没前途。

仔细一看发现这个 dp 满足四边形不等式，那么就有决策单调性了。考虑二分队列。

首先，先按照 A_i 对每条边排序，记排序后的边数组为 e。依次将 e_i 标号称作 id_i。

依次令 id_i\larr cs_{X_{e_i}},rf_{X_{e_i},id_i}\larr e_i,cs_{X_{e_i}}\larr cs_{X_{e_i}}+1。记 Val_{i,j}=c_i+f_j+T_{X_i}\times Cost_{B_j+1,A_i-1}。

由于有星球的限制，所以对每个星球开一个 deque 叫做 dq_i。dq_i 的每一个元素都是一个三元组 (x,l,r) 满足 x 对 rf_{i,l}\sim rf_{i,r} 做决策。

考虑向 dq_i 中插入一个 x：

• 首先，记队尾三元组为 (x',l',r')。若 Val_{rf_{i,l'},x'}>Val_{rf_{i,l'},x} 那么意味着 x 比 x' 在 rf_{i,l}\sim rf_{i,r} 上更优，直接删掉三元组继续下一次判断；
• 否则，二分出一个 mid 满足 Val_{rf_{i,mid},x'}>Val_{rf_{i,mid},x},Val_{rf_{i,mid-1},x'}\le Val_{rf_{i,mid-1},x}，修改队尾三元组 (x',l',r') 至 (x',l',mid-1)，新增三元组 (x,mid,cs_i-1)；
• 若某时刻队中不存在元素，直接新增三元组 (x,0,cs_i-1)。

记如上操作为 add(i,x)。

再考虑计算一条边 i 的答案：

• 首先，记 dq_{X_i} 队头三元组为 (x,l,r)。若 r<id_i 则说明 x 不在 i 上最优，直接删掉三元组继续下一次判断；
• 否则直接令 f_i=Val(i,x)；
• 若某时刻 dq_{X_i} 中不存在元素，直接设置 f_i=+\infty。

记如上操作为 ask(i)。

每个星球维护一个小根堆 pq_i，按照 B_j 从小到大排序。在按 e_i 顺序转移时按如下方式执行操作：

• 若 pq_{X_{e_i}} 队头 x 满足 B_x\le A_{e_i} 则执行 add(X_{e_i},x) 并删除队头继续判断；
• 否则执行 ask(e_i)；
• 接下来在 pq_{Y_{e_i}} 中插入 e_i。

时间复杂度 O(N\log^2N)。