Description：

一个 $S$ 的循环节 $T$ 表示为可以找到一个正整数 $k$ 使得 $S$ 是 $T^k$ 的前缀。一次操作会在字符串尾部添加一个字符，并且你需要在每次操作后输出最小循环节长度。要求可持久化与在线。

$1\leqslant n\leqslant 3\times 10^5$

Solution：

首先字符串形成了一个树的结构，答案是 $i-nxt[i]$ ，显然可以暴力 $KMP$ ，但 $KMP$ 的复杂度依赖均摊分析，这样复杂度是假的。

考虑怎么快速跳 $nxt$ ，如果 $c[j+1]=c[i]$ ，那么 $nxt[i]=j+1$ ，如果不等于的话，分类讨论一下：

如果 $2\times nxt[j]\leqslant j$ ， $j=nxt[j]$ ，如果 $2\times nxt[j]>j$ ，那么显然 $j$ 有 $j-nxt[j]$ 这样一个循环节，考虑如果暴力跳过这些 $nxt$ 会发生什么，会发现其实是跳过了一个循环节，那么我们就不用一步一步跳，而是一下把这所有的循环节都跳过去，反正在循环节上 $j+1$ 永远不等于 $i$ ，即 $j=j\%(j-nxt[j])$ ，我们每次让 $j$ 至少缩小一半，因此至多跳 $\log$ 次，然后需要在线构造倍增定位节点就行了。

时间复杂度 $O(n\log^2n)$ 。

Code：