qoj#1174 Lights On The Road

给定正整数 $n,K$ 及长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。

定义一个 $\{1,2,\dots,n\}$ 的子集 $S$ 为合法的，当且仅当 $\forall 1\leq i\leq n,\{i-1,i,i+1\}\cap S\neq\varnothing$。定义一个合法子集 $S$ 的权值为 $f(S)=\displaystyle\sum_{i\in S}a_i$。

要求输出将所有合法 $S$ 的 $f(S)$ 从小到大排序后的前 $K$ 个值，不足 $K$ 个用 $-1$ 补齐。

$1\leq n,K\leq 2.5\times10^5$，$0\leq a_i\leq 10^9$。

对于此类前 $K$ 小问题，一个常用做法是构建可能答案之间的前后继关系，并使每个状态的直接后继较少。如果本题求的是前 $K$ 大，确实存在类似做法。但对于前 $K$ 小，将直接后继限制在常数个比较困难。

换另一种思路。考虑这样一个问题：定义 $g(S)=\displaystyle\prod_{i\in S}a_i$，求所有合法子集 $S$ 的 $g(S)$ 之和。那么就能很自然地得到动态规划做法：定义 $g_{i,0/1/2}$ 表示考虑了 $1\sim i$，且 $i-1,i$ 都不在 $S$ 中/ $i - 1$ 在 $S$ 中 $i$ 不在/ $i$ 在 $S$ 中，此时所有 $g(S)$ 之和。这实际上可以看作构建了一张 DAG，将答案表示成所有起点到终点的路径的权值积之和。

那么回到原问题上，可以构建类似的 DAG，并将答案看作是求图上起点到终点的 $K$ 短路，具体地：设点 $i_{0/1/2}$ 表示和上面动态规划一样的状态，那么对于所有 $1\leq i<n$，连带权有向边 $(i_0,(i+1)_2,a_{i+1}),(i_1,(i+1)_0,0),(i_1,(i+1)_2,a_{i+1}),(i_2,(i+1)_1,0),(i_2,(i+1)_2,a_{i+1})$，同时建立起点 $s$ 和终点 $t$，并连边 $(s,1_0,0),(s,1_2,a_1),(n_1,t,0),(n_2,t,0)$，那么在这张点数边数均为 $O(n)$ 的 DAG 上求出 $s$ 到 $t$ 的 $K$ 短路即为答案。

Eppstein 算法可以以 $O(n\log n+m+K)$ 复杂度求出任意 $n$ 个点，$m$ 条边的非负权有向图中给定起点 $s$ 和终点 $t$ 的 $K$ 短路（以下所有 $K$ 短路均允许路径中经过重复的点和边）。而如果最短路树已经给出，则可以做到 $O(n+m+K)$ 的复杂度（见参考资料 2）。

下面将介绍一种复杂度为 $O(n\log m+m+K\log K)$ 的 $K$ 短路算法。

首先，求出所有点到 $t$ 的最短路，并建出最短路树。设点 $i$ 到 $t$ 的最短路权值为 $d_i$，最短路树即为对于每个不为 $t$ 且可以到达 $t$ 的点 $u$，找到一条出边 $(u,v,w)$，满足 $d_u=d_v+w$，则将 $u$ 的其它所有出边删去，并将 $t$ 的所有出边删去。无法到达 $t$ 的点显然可以删去，下文中假设所有点均能到达 $t$。不难说明剩下的点和边会形成一棵以 $t$ 为根的内向树。

考虑 $s$ 到 $t$ 的每条不完全在最短路树上的路径，设经过的非树边依次为 $(u_1,v_1,w_1),(u_2,v_2,w_2),\dots,(u_k,v_k,w_k)$，则对于 $1\leq i<k$，有 $u_{i+1}$ 为 $v_i$ 在最短路树上的祖先。事实上，可以说明任意的 $s$ 到 $t$ 的路径可以与满足这一条件的非树边序列一一对应。对于每条非树边 $(u,v,w)$，定义其偏移量为 $d_v+w-d_u$ （由最短路知这个值非负），那么一条路径的权值即为最短路加上其对应的非树边序列的偏移量之和，即 $d_s+\displaystyle\sum_{i=1}^k(d_{v_i}+w_i-d_{u_i})$。

现在构建一张新图，点集不变，边集为对于每个点 $u$，对于原图中其所有祖先 $u^{\prime}$ 的非树出边 $(u^{\prime},v,w)$，新图中建边 $(u,v,d_v+w-d_u)$。那么求出新图从 $s$ 开始的不固定终点的 $K$ 短路，即可求出原图 $s$ 到 $t$ 的 $K$ 短路。

新图的边集大小可以达到 $O(nm)$，直接全部求出不可接受。但注意到一个点的出边一定是从小到大考虑，符合小根堆的应用场景，故可以用持久化可并堆得到新图上每个点的出边。在求新图 $K$ 短路时，将状态 $(dis,heap)$ 放入优先队列中，其中 $dis$ 表示当前路径长度，$heap$ 为当前路径终点还没考虑过的出边构成的小根堆。每次取出 $dis+w(heap.top)$ 最小的 $(dis,heap)$，得到一条权值为 $new\_dis=dis+w(heap.top)$ 的路径，并将 $heap$ 堆顶弹出得到 $new\_heap$，那么将 $(dis,new\_heap)$ 和 $(new\_dis,out\_edge_{to(heap.top)})$ 放入优先队列（如果使用左偏树等二叉堆，也可以不用 $new\_heap$，而是直接将 $heap$ 的左右子树分别加入）。这样前 $K$ 条从优先队列取出的路径即为 $K$ 短路。

构建最短路树可以用 Fibonacci 堆优化 Dijkstra 算法做到 $O(n\log n+m)$，求新图边集可以用线性建堆和持久化可并堆做到 $O(n\log m+m)$，最后的优先队列中总共会出现 $O(K)$ 个元素，故总复杂度 $O(n\log m+m+K\log K)$。