P10209 [JOI 2024 Final] 路网服务 2 / Road Service 2
容易发现我们原网格图上构成了若干个联通块，每个联通块对应一个行上的区间 \([L,R]\)，那么对于这个块内的一个点，它能到达的最靠下的就是第 \(R\) 行。
此时考虑 \(C_i=1,k=2\) 的部分分，我们找出起点对应的联通块，第一步我们肯定选择打通 \(R\) 这一行最优；接下来我们找出 \(R\) 这一行上所有点对应联通块的 \(R\) 的最大值，我们下一步一定会打通这个 \(R\)。以此类推，直到我们走到超过终点的 \(L\) 的时候就结束了。暴力做是单次 \(O(n)\) 的。我们令 \(nxt_i\) 表示打通第 \(i\) 行之后能到达的最靠下的行，那么实际上这个过程就是不断跳 \(nxt\) 的过程，很显然可以倍增优化到 \(O(\log n)\)。
然后考虑 \(C_i=1\) 的部分分。我们先找出每一个点对应联通块的区间 \([L,R]\)，去重之后去掉包含的区间，这样剩下的区间有单调性，我们按照左端点排序。此时我们相当于要做 \(k\) 次上面的倍增操作，每一次跳到进入下一个区间前的最后一步，然后打通这个区间的操作单独转移一次指针即可。这样的话复杂度就是 \(O(\sum k\log n)\) 的。
然后我们将上面的做法进行推广。首先由于有 \(C_i=2\)，所以我们的代价不再是跳跃的次数。设 \(dp_i\) 表示花费代价为 \(i\)，能打通的最靠右的位置，单次转移只需要最后的两个位置即可。然后我们同样考虑倍增优化这个过程，朴素的思路是设 \(f_{i,j}\) 表示打通 \(i\) 之后花费 \(2^j\) 的代价能打通的最靠下的位置。但是此时我们不只有 \(0\to 2^j\to 2^{j+1}\) 这一种转移，还有一种情况是 \(0\to 2^j-1\to 2^j+1\to 2^{j+1}\)，这是传统倍增所无法处理的。因此设 \(f_{i,j,0/1}\) 表示花费为 \(2^j-1\) / \(2^j\) 打通的最靠下的位置。
然后此时我们用倍增优化这个 dp 过程即可。和上面的处理方式类似，我们从当前位置出发倍增到进入下一个区间前的最后一个状态，然后区间内的转移单独做一次即可。复杂度依然是 \(O(\sum k\log n)\) 的。