一类序列上的最短路问题-倍增

CF1246F Cursor Distance

考虑对于每一个 $i$ ，求出至多走 $k$ 步就能够到达它的位置所构成的区间 $[L_{i, k}, R_{i, k}]$ 。我们只要对每个 $i$ 分别求出 $\sum_{k} L_{i, k}, \sum_{k} R_{i, k}$ 就能得到答案。

最短路不一定是单向的（比如对于baaaaac，从b走到最后一个a），所以 $L, R$ 可能不独立，不能直接倍增计算 $L, R$ 的和。

进一步观察， $R_{i, k + 2}$ 的取值与 $[L_{i, k + 1}, L_{i, k})$ 中的位置有关的必要条件是 $[L_{i, k + 1}, R_{i, k + 1}]$ 的字符集大于 $[L_{i, k}, R_{i, k}]$ 的字符集；如果 $[L_{i, k + 1}, R_{i, k + 1}], [L_{i, k}, R_{i, k}]$ 字符集相同，则 $R_{i, k + 2}$ 就只与 $R_{i, k + 1}$ 和 $[L_{i, k}, R_{i, k}]$ 的字符集大小有关。

对于每个 $i$ ，当 $k$ 从 $0$ 取到 $+ \infty$ 的时候， $[L_{i, k}, R_{i, k}]$ 的字符集大小只会变化 $| Σ |$ 次（ $| Σ |$ 表示字符集大小）。故而，我们可以枚举当前这些区间的字符集大小，这时候 $L, R$ 是独立的，可以直接倍增求出它们的和。

实现细节上，在最外层枚举区间的字符集大小 $t$ ，然后对每个位置 $i$ 处理出 $f l_{i}$ ——表示当 $L$ 为某个满足 $[L, i]$ 字符集大小为 $t$ 的位置， $R = i$ 的时候，跳一步能够把 $R$ 扩展到哪里；以及类似定义的 $f r_{i}$ 。预处理出 $f l_{i}, f r_{i}$ 倍增的结果。然后对每个 $i$ 从大到小枚举 $j$ ，然后看它现在的区间端点扩展 $2^{j}$ 次以后，区间内是否仍然只有 $t$ 种字符。

Code

LOJ6435 「PKUSC2018」星际穿越

参考这篇blog

设 $f_{i, k}$ 为从 $i$ 出发，走 $k$ 步能够到达的最靠左的点。则有 $f_{i, k + 1} < f_{i, k}$ 。

显然 $f_{i, 1} = l_{i}$ 。

然后是 $f_{i, 2} = min_{j \geq l_{i}} {l_{j}}$ ：

对于 $j \in [l_{i}, i)$ ， $i$ 可以在第一步走到 $j$ ；
对于 $j > i$ ，如果 $l_{j} \leq i$ 我们可以选择在第一步走到 $j$ ，否则 $l_{j} > i$ ， $l_{j}$ 一定不会被 $min_{x \geq l_{i}} {l_{x}}$ 取到。

对于 $f_{i, k} (k > 2)$ ，有 $f_{i, k} = min_{j \in [f_{i, k - 1}, f_{i, k - 2})} {l_{j}} = min_{j \in [f_{i, k - 1}, i)} {l_{j}}$ 。由于显然 $f_{i, k} < f_{i, 2} \leq min_{j \geq i} {l_{j}} (k > 2)$ ，所以也可以写作 $f_{i, k} = min_{j \in [f_{i, k - 1}, n]} {l_{j}}$ 。这个式子中 $f_{i, k}$ 的取值与 $i$ 无关而只与 $f_{i, k - 1}$ 有关，所以可以倍增求出 $k = 2^{j}$ 时的 $f_{i, k}$ 和 $\sum_{x \in [1, k]} f_{i, x}$ 。

实现上，可以强制先走 $k = 1$ 的第一步 $f_{i, 1} = l_{i}$ ，这样的话之后的每一步的转移都满足 $f_{i, k} = min_{j \geq f_{i, k - 1}} {l_{j}}$

Code