题目定义了 “一个半回文串”，其实就是形如abab，是一个长度3n-2的字符串，其中子串[1,2n-1]是长度为奇数的回文串，[n,3n-2]同样是长度为奇数的回文串。
那么所求可转化如下。
首先，因为回文串长度均为奇数，因此我们不需要考虑偶数长度的回文子串。
假设位置i的字符作为回文子串的中心时的最大回文半径为r[i]（这个显然可以通过马拉车算法预处理出），则我们要求的是这样的 (i,j)的对数：
假设i>j，则有 i-r[i]>=j && j+r[j]>=i，因为只有这样的一对位置，才可以保证能形成符合要求的“一个半回文串”。
这个感觉很像是一个二维偏序问题。
对所有的(i-r[i],i)按i-r[i]从小到大排序，从小到大枚举j，因为只有i-r[i]小于等于当前j的i才可能与之形成符合要求的 (i,j)，因此将所有i-r[i]小于等于当前j的i插入树状数组（即将对应位置+1），然后，统计在(j,j+r[j]]之间的和即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ll long long
const int MAXN=5e5+5;
char Ma[MAXN];
int Mp[MAXN];
void Manacher(char s[],int len){
//因为只需要求奇数长度的回文串，所以除了起始字符外不用添加特殊字符 int l=len+1;Ma[0]='$';Ma[l]=0;int mx=0,id=0;for(int i=0;i<l;i++){Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;if(i+Mp[i]>mx){mx=i+Mp[i];id=i;}}
}
int t;
int c[MAXN];
int lowbit(int x){return x&(-x);
}
void add(int x,int z=1){while(x<MAXN){c[x]+=z;x+=lowbit(x);}
}
int query(int x){int res=0;while(x>0){res+=c[x];x-=lowbit(x);}return res;
}
struct node{int d,pos; bool operator<(const node &p)const{//按差值排序 return d<p.d;}
}a[MAXN];
int main(){scanf("%d",&t);while(t--){scanf("%s",Ma+1);int len=strlen(Ma+1);Manacher(Ma,len);mst(c,0);for(int i=1;i<=len;i++){ Mp[i]--;}ll ans=0;int cnt=0;for(int i=len;i>=1;i--){ a[cnt].d=i-Mp[i];a[cnt].pos=i;cnt++;}sort(a,a+cnt);for(int i=1,j=0;i<len;i++){while(j<cnt&&a[j].d<=i){add(a[j].pos);j++;}ans+=query(i+Mp[i])-query(i);}cout<<ans<<"\n";}return 0;
}