你真的会 manacher 吗？
模拟赛遇到的，记录一下。
manacher 可以求出每个点的回文半径 $d_i$——但是我们有的时候需要的信息不止这个。比如说，我们想要统计所有回文串的信息。
对于一些尾删、尾插方便但不方便合并的信息，manacher “暴力拓展时只会在尾部插入”的性质尤为可贵。但是我们还会从之前一个位置继承过来，这时可能会将之前的答案截断只留一段前缀，这时暴力尾删的复杂度对吗？
答案是，可以是对的，但是你得确保你写出了“正确的” manacher。
记下标 $i$ 继承了 $fa_i$ 的答案，则只有当 $i+d_{fa_i}-1>r_i$ 的时候才会截断。暴力尾删的计算量是 $\sum i+\blue{d_{fa_i}-1}-r_i \le \sum i+\blue{(r_i-fa_i)}-r_i=\sum{i-fa_i}=\sum2(i-mid_i)$，其中 $mid_i$ 表示得到 $[l_i,r_i]$ 这一区间的下标。
只要你在 manacher 中在 $i+d_i-1\ge r$ 时更新 $[l,r]$（而不是 $i+d_i-1> r$ 时），每次尾删完就一定会将 $mid$ 改成 $i$，因此均摊下来依然是线性的。
你要是在四川省集前发布这篇文章我就可以少垫一次底了 /ll
然而这道题来源应该就是四川省集，令人感概
orz