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}]$的字符集大小只会变化$|\Sigma|$次（$|\Sigma|$表示字符集大小）。故而，我们可以枚举当前这些区间的字符集大小，这时候$L,R$是独立的，可以直接倍增求出它们的和。
实现细节上，在最外层枚举区间的字符集大小$t$，然后对每个位置$i$处理出$fl_i$——表示当$L$为某个满足$[L,i]$字符集大小为$t$的位置，$R=i$的时候，跳一步能够把$R$扩展到哪里；以及类似定义的$fr_i$。预处理出$fl_i,fr_i$倍增的结果。然后对每个$i$从大到小枚举$j$，然后看它现在的区间端点扩展$2^j$次以后，区间内是否仍然只有$t$种字符。
LOJ6435 「PKUSC2018」星际穿越
设$f_{i,k}$为从$i$出发，走$k$步能够到达的最靠左的点。则有$f_{i,k+1} < f_{i,k}$。
显然$f_{i,1} = l_i$。
然后是$f_{i,2} = \min_{j \ge l_i} \{l_j\}$：
- 对于$j\in [l_i,i)$，$i$可以在第一步走到$j$；
- 对于$j>i$，如果$l_j\le i$我们可以选择在第一步走到$j$，否则$l_j > i$，$l_j$一定不会被$\min_{x\ge 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} \le \min_{j\ge 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\ge f_{i,k-1}} \{ l_j\}$