parlidrome

不懂，搜了一下题解
https://blog.csdn.net/wl16wzl/article/details/81164248

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=500010;
ll c[maxn];
int n;

inline int lowbit(int x){
	return x&(-x);
}

void update(int idx,int v){
	while (idx<=n){
		c[idx]+=v;
		idx+=lowbit(idx);
	}
}

ll query(int  x){
	ll ans=0;
	while (x){
		ans+=c[x];
		x-=lowbit(x);
	}
  return ans;
}


char str[maxn];
char tmp[maxn<<1];
int Len[maxn<<1];
int INIT(char *st){
	int i,len=strlen(st);
	tmp[0]='@';
	for (int i=1;i<=2*len;i+=2){
		tmp[i]='#';
		tmp[i+1]=st[i/2];
	}
	tmp[2*len+1]='#';
	tmp[2*len+2]='$';
	tmp[2*len+3]=0;
	return 2*len+1;
}
int MANACHER(char *st,int len){
	int mx=0,ans=0,po=0;
	for (int i=1;i<=len;i++)
	{
		if (mx>i)
		  Len[i]=min(mx-i,Len[2*po-i]);
		  else  
		  Len[i]=1;
		while (st[i-Len[i]]==st[i+Len[i]])
		  Len[i]++;
		if (Len[i]+i>mx){
			mx=Len[i]+i;
			po=i;
		} 
		ans=max(ans,Len[i]);
	}
  return ans-1;
}

vector<int> g[maxn];
int p[maxn];
int main(){
  int T;
  scanf("%d",&T);
  while (T--){
  	scanf("%s",str);
  	n=strlen(str);
  	int len0=INIT(str);
  	MANACHER(tmp,len0);
  	memset(c,0,sizeof(c));
  	for (int i=1;i<=n;i++)
  	 g[i].clear();
  	 
  	for (int i=2;i<len0;i+=2){
  		p[i/2]=Len[i]/2-1;
  		g[i/2-p[i/2]].push_back(i/2);
	  }
	  ll ans=0;
	  for (int i=1;i<=n;i++){
	  	for (int j=0;j<g[i].size();j++)
	  	  update(g[i][j],1);
	  	  ans+=query(i+p[i])-query(i);
	  }
   printf("%lld\n",ans);
  }
  return 0;
} 

题目中要求的串，可以概括为两个回文串的组合：_____ i ____ j _____

以 i 和以 j 为中心的两个回文串拼接起来，注意 i 的回文串范围要覆盖 j，j 的回文串范围要覆盖 i

设p[i]是以 i 为中心的回文串覆盖半径（不包括 i ）

那么要符合三个条件：j>i ; j<=i+p[i] ; i>=j-p[j] ;

先用Manacher算法算出以每个点为中心的最长回文串长度

再按照 i 从1~n维护满足( j-p[j]>=i )的 j 在树状数组里，然后查询[ i+1,i+p[i] ]范围内的 j 有多少个，加起来就是答案