JZOJ 4645. 【NOI2016模拟7.16】基因改造计划

题目

给定一个字符集大小为4的，长度为n的字符串。
m个询问，询问区间[l,r]的回文字符串有几个。
数据范围：

题解

这题挺经典的。
有很多可以骗分的算法。
骗个20分？
m很小，直接暴力m次manacher。
骗个45-75分？
莫队。
关键是回文自动机我不会啊！！！！！
考虑如何用[l,r−1]$[l,r-1]$的答案迅速算出[l,r]$[l,r]$的答案。
此时增加量为右端点为r的，左端点为[l,r]$[l,r]$的回文串的个数。
以中心为思考方向的回文串题目，通常用Manacher做；但是如果以左右端点为思考方向，用回文自动机。
若要查询右端点为r的，左端点为[l,r]$[l,r]$的回文串的个数，则相当于在回文树的parent树上查询tree[r]的祖先中，对应回文长度不超过r−l+1$r-l+1$的节点个数。
可以用倍增（常数较大）或树剖搞定。
可我不会啊。
期望复杂度O(mn−−√log n)$O(m\sqrt{n}logn)$。
如何AC本题？
考虑Manacher，此时弄出了长度为2n+1$2n+1$的len[]$len[]$，表示以i$i$为中心最长扩展长度。
若s[i]$s[i]$为分隔符，则在原字符串中有len[i]2$\frac{len[i]}{2}$，否则为len[i]+12$\frac{len[i]+1}{2}$。
对于原询问区间[l,r]$[l,r]$，对应新的询问区间为[2l−1,2r+1]$[2l-1,2r+1]$。
令L=2l−1,R=2r+1$L=2l-1,R=2r+1$。
则答案为

考虑怎么算。肯定要分类讨论min(k−L,R−k)$min(k-L,R-k)$
当k−L≤R−k$k-L\le R-k$即k≤l+r$k\le l+r$时，求
考虑用离线，当k一定时，以L$L$为自变量可以得出一个函数，用线段树存k=x时的一次的系数和常数项。
将所有拐点的横坐标储存一下，给询问排个序，扫一扫。
R−k≥k−L$R-k\ge k-L$情况类似。