p10538 sol

我的二分队列决策单调性启蒙题。设 $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$：

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

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

记如上操作为 $ask(i)$。

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

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