D, E: Silly_Tape的字符串

容易发现，一个串 S 内的奇数长度的回文子串的数量随着长度减少单调非递减，因为对于一个长度为 K 的奇数长度回文串 P,

P[2:K-1], P[3:K-2] ... (下标从1开始) 显然也是奇数长度的回文串。

因此有一个很显然的结论: 设 L 为字符串 T 内最长奇数长度回文串的长度，带入连续奇数求和公式，则有字符串 T 的总价值为 ceil(L / 2) ^ 2

同时因为奇数长度回文子串的数量具有单调性，可以通过二分查找来确定最大的 L，接下来考虑如何检查二分查找每一步选择的中点 mid 是否可行。

对串 T 进行一遍 Manacher 算法获取 T 内以每个下标 i 为中心的最长回文串长度 D[i] 后，容易发现上面的问题实际上是查询 D 中 满足 floor(mid / 2) + 1 <= i <= D的长度 - floor(mid / 2) 且 D[i] >= mid 的 i 的数量。

对于 easy version，因为只需要存在一个长度为 L 的奇数长度回文子串就可以，我们只需要查询区间 D[i] 的最大值，使用 ST 表即可。

对于 hard version，使用可持久化线段树即可。