ABC417G

_jimmywang_ · 2025-08-03 00:36:37 · 题解

智力巅峰体验卡。

考虑暴力跳的过程。我们发现跳到组成该串的两个串之间的较短串的次数是 O(\log L) 的（L 是串长），因为这样一次串长至少减半。因此我们考虑快速在两次“跳较短串”之间转移。

容易发现这等价于我们要能够维护极长的“连续跳较长串”的过程，这个可以倍增实现。具体的，维护从当前串的哪个区间 [l,r] 出发，可以连续跳 2^k 次较长串即可。注意处理串长 >10^{18}（不然上面那个 \log L 是错的，串长会达到指数级，应及时截断）和这个区间不存在的情况即可。

复杂度的话，倍增数组直接在加入一个新串的时候在线处理；求解答案需要 O(\log L) 次跳较短串，每次需要 O(\log n) 的倍增找位置，故总复杂度 O(n\log n\log L)。