传送门:https://vjudge.net/contest/391081#problem/A

题目大意: 给你一个字符串，让你统计其中 两个等长且奇长的互相重叠组合而成的回文子串的个数.

题目思路:类似于HDU5371.都是Manacher+数据结构维护

解法一：树状数组

我们通过Manacher得到p数组。问题可以转化为:

可以看出这是区间求和问题。又因为可以离线所以考虑排序。

1.我们对 j + len[j] - 1 降序排序，然后有序循环 i 从 n -> 1.

2.将所有 j + len[j] - 1 >= i 的j一次贡献插入树状数组，然后对[i - len[i] + 1 , i - 1]区间求和(求个数).如此往复.

解法二：主席树

等效于求区间>=某个值的个数。直接主席树上差分一下即可。