GDKOI2021提高组Day1C回文
1686+
作者：crxis 发布：2021-02-05 分类：字符串
题目大意：给定一个长度为n的字符串，m次询问，每次回答区间[l, r]内字符串的最大回文长度。
解题思路
使用Manacher算法预处理出以每个位置为中心的最长回文长度，并用ST表预处理区间回文长度最大值，对于每次询问，二分答案即可。
首先，马拉车算法可以在O(n)得到每个位置（包括空隙）的最长回文长度；
接着，使用倍增得到区间回文中心最大回文长度；
最后，二分答案，长度为m的字符串，在区间[l, r]内，回文中心的范围约l+m>>1~r-m>>1，具体边界可以慢慢考虑。是否有满足要求的答案，就看这里的最大回文长度是否达到m即可。
程序实现
