用到的知识点

Manacher+线段树/树状数组
Manacher算法是一种能在O(n)复杂度内求出每个点最大回文半径的算法，没学过的点这里

解题思路

暴力解法

我们第一个想到的肯定是暴力解法：枚举每一个字符串，判断是否为题目要求的one-and-half串，然后统计答案
时间复杂度：O(n^3) 肯定不行，于是尝试优化

考虑使用Manacher算法进行优化

为什么想到Manacher呢？
因为题目与回文串有关，往这方面想说不定就做出来了。
我们先跑一遍Manacher，于是得到了所有点的最大回文半径。

重点1

此处我们不需要引入'#' ，因为根据题目要求，我们所需的回文串一定是两个相连的奇回文串[1,2n-1]和[n,3n-2]

构造几组数据，研究普遍规律，如：
$图片说明$
其中符合题目要求的有：abab,baba,abab,baba,abab,abababa,bababab,一共7个，我们很容易发现这7个回文串的共同规律：

重点2

如果i,j(i<j)为两个回文串的中心，且i+r[i]-1>=j&&j-r[j]+1<=i(i和j的最大回文串在[i,j]这部分是完全一样的），则[2i-j-1,2j-i-1]为题目要求的回文串

于是我们得到了一个相对于暴力更优的算法：
对于每个点i，我们从i循环到i+r[i]-1,其中每有一个j符合j-r[j]+1<=i,答案就+1
即： $图片说明$
总体的复杂度为O(n^2)
继续优化！
观察上面的式子，考虑对于每一个j，它对哪些i产生了贡献？它对所有i>=j-r[j]+1产生了贡献，那么我们可以将所有的点j按照j-r[j]+1的大小来升序排序，然后循环i，不断往后找j,如果j-r[j]+1的值小于等于i，就使j点的值+1，此时[i+1,i+r[i]-1]区间的和即为与i构成的one-and-half串的个数，即单点更新，区间查询！

使用线段树/树状数组进一步优化

按照上面的思路：先跑一遍Manacher,O(n)预处理出所有点的最大回文串半径r[i],然后按i-r[i]+1的大小升序排序，然后循环i，对于每个j，如果j-r[j]+1小于等于i就j点+1，当所有符合要求的j都更新完之后，查询[i+1,i+r[i]-1]区间的和，加到答案上
代码实现：

        Manacher();
        ans=0;
        for(int i=1;i<n;++i)node[i]=(Node){i-r[i]+1,i};
        sort(node+1,node+n,cmp);
        int now=1;//当前已经添加的点 
        for(int i=1;i<n;++i){
            while(now<n&&node[now].l<=i){//将后面的可到达的点加入树状数组 
                add(node[now].pos,1);
                now++;
            }
            ans+=query(i+r[i]-1)-query(i);//i和i可到达的，且可到达i的点都是one-and-half串 
        }

在此过程中涉及的操作的复杂度如下：
1.Manacher复杂度为O(n)
2.排序复杂度为O(nlogn)
3.循环中i与j均摊O(n)的复杂度，每次查询和更新是O(logn)，所以，这部分复杂度为O(nlogn)
总的复杂度O(nlogn)

本题坑点

1.要开longlong！！！

2.多组数据，记得重置数组

完整代码

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<algorithm>
using namespace std;
const int mx=505050;
int n;
int r[mx];//每个点的最大回文半径 
char s[mx];
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
void Manacher(){
    s[0]='~';
    int len=strlen(s);
    s[len]='@';
    n=len;
    int mr=0,mid=0;
    for(int i=1;i<len;++i){
        if(i<=mr)r[i]=min(r[2*mid-i],mr-i+1);
        else r[i]=1;
        while(s[i-r[i]]==s[i+r[i]])++r[i];
        if(i+r[i]>mr){
            mr=i+r[i]-1;
            mid=i;
        }
    }
}
struct Node{
    int l;//该点可到达的最左点 
    int pos;//该点的位置 
}node[mx];
bool cmp(Node a,Node b){
    return a.l<b.l;
}
int tree[mx];
#define lowbit(i) i&-i
void add(int i,int x){
    while(i<n){
        tree[i]+=x;
        i+=lowbit(i);
    }
}
int query(int i){
    int ans=0;
    while(i>0){
        ans+=tree[i];
        i-=lowbit(i);
    }
    return ans;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>s+1;
        Manacher();
        long long ans=0;
        for(int i=1;i<n;++i)node[i]=(Node){i-r[i]+1,i};
        sort(node+1,node+n,cmp);
        int now=1;//当前已经添加的点 
        for(int i=1;i<n;++i){
            while(now<n&&node[now].l<=i){//将后面的可到达的点加入树状数组 
                add(node[now].pos,1);
                now++;
            }
            ans+=query(i+r[i]-1)-query(i);//i和i可到达的，且可到达i的点都是one-and-half串 
        }
        printf("%lld\n",ans);
        memset(tree,0,sizeof(tree));
    }
    return 0;
}

Palindrome__题解