ABC417G

智力巅峰体验卡。

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

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

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