赛时过的人少估计是因为难调。
考虑修改一个字符的贡献，会使得所有以该字符为瓶颈的回文串增加长度，同时会使得原来所有最长回文串经过该位置的位置减少长度。换个视角，不妨通过二分+哈希分别预处理出以每个位置为回文中心的最长回文串长度、以及修改一个字符后的最长回文串长度，则对于前者，会对区间造成等差序列的负贡献；后者和前者的差，会对瓶颈的特定字符造成正贡献。
最后统计每个位置每个字符的贡献之和取最大值即可。输出方案时，先从前到后尽可能修改到比原串更小的字符，若无解则考虑能否保留原串，否则从后到前、从原串中该位置上的字符到 \(z\) 尝试修改。
时间复杂度 \(O(n\log n+26n)\)。
标签：字符,Edu160F,位置,CF,原串,修改,长度,Problem,回文 From： https://www.cnblogs.com/ydtz/p/17916071.html