如何优雅地求区间本质不同回文串

如何优雅地求区间本质不同回文串

0. $O(n^2)$

直接暴力。一点都不优雅。

1. $O(n\sqrt n\Sigma)$

允许双向加的回文树，再套一个(在线)莫队即可。

太拉了，还难写。

2. $O(n\log^2 n)$

考虑离线，依次加入字符，维护每个 $i$ 作为左端点的答案。

考虑维护差分数组，这样每次答案是一段后缀和。

思考一种暴力思路：在回文树上，对于每个串 $s_j$ 记录最晚出现位置 $p_j$。

设一次加入后字符串长度为 $n$，本质上是对于回文树上这个字符串到根路径上所有字符串 $s_j$，在 $p_j$ 处 $-1$，在 $n-|s_j|$ 处 $+1$，并将 $p_j$ 改为 $n-|s_j|$。

直接做显然会被卡掉。

考虑一个事情，每个回文串的 border 可以表示为 $O(\log n)$ 个等差数列。注意到一个性质：对于回文串 $s$，如果存在长度 $q(q>\frac{|s|}2)$ 的回文前缀，那么一定存在 $|s|-q$ 的周期。换句话说，如果存在长度为 $p,q(p>q>\frac{|s|}{2})$ 的回文前缀，那么一定存在 $2q-p$ 是回文前缀。

所以任意两个等差数列都有前者的首项大于后者的末项的两倍。

并且观察到一个事实：对于等差数列 $s_i=u^i+s_0$，一定有 $p_i=-i|u|+p_0$。换句话说这个字符串的贡献是当前左端点到后一项的左端点。

贡献和的并就是最后一个位置为右端点，整个区间上一次出现位置为左端点的区间。

换句话说，我们只需要贡献所有不存在长度 $>\frac{|s|}2$ 的回文串后缀的后缀 $s$ 即可。这样的 $s$ 最多 $O(\log n)$ 个，具体求出可以直接在回文树上预处理。

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

3. $O(n\log n)$

对于任意字符串 $s$，如果 $s$ 不是整循环串，那么 $s$ 的所有循环位移中至多只有 $2$ 个是回文串。可以想象一个定义在圆上的函数，如果有两条不重合的对称轴，那么一定是一个周期函数。

考虑原串的 Runs $(l,r,p)$，显然 $s[l:l+p-1]$ 不是整循环串（Runs 的定义），那么至多只有 $2$ 个极长整循环周期为 $p$ 的回文串。

可以发现上述算法中，每个极长整循环的回文串只有在循环节处会产生 $O(\log n)$ 的处理代价。而所有极长整循环的回文串指数之和不超过 Runs 的指数之和的两倍，故是 $O(n)$ 的。

所以上面那个算法其实是 $O(n\log n)$ 的。