刚开始是听说了要用manacher采取写的，但是不难看出要使用manacher，因为题目要求的1个半回文串，其实就是两个回文中心的交集，你要找两个回文中心，让它们的回文半径可以互相覆盖即可。问题转化成了对于一个回文中心，它覆盖的左侧的所有回文中心中（ 向右覆盖的范围超过i ）这样的点的数量。这样就变成了求区间中大于x的数的个数，可以用主席树解决。
#include<iostream> #include<cstring> #include <string> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e6+20; const int maxm=2e7+20; char s[maxn],s_new[maxn]; int p[maxn]; int init() { int len=(int)strlen(s); s_new[0]='$'; s_new[1]='#'; int j=2; for(int i=0;i<len;i++) { s_new[j++]=s[i]; s_new[j++]='#'; } s_new[j]=0; return j; } int manacher() { int len=init(); int id=0,mx=0; for(int i=1;i<len;i++) { if(i<mx) p[i]=min(p[2*id-i],mx-i); else p[i]=1; while(s_new[i-p[i]]==s_new[i+p[i]]) p[i]++; if(mx<i+p[i]) { id=i; mx=i+p[i]; } } return len; } int n,m,cnt; int tree[maxn],ls[maxm],rs[maxm],sum[maxm]; void update(int k,int pre,int &now,int l,int r){ now=++cnt; ls[now]=ls[pre]; rs[now]=rs[pre]; sum[now]=sum[pre]+1; if(l==r){ return; } int m=(l+r)>>1; if(k<=m) update(k,ls[pre],ls[now],l,m); else update(k,rs[pre],rs[now],m+1,r); } int query(int a,int b,int l,int r,int L,int R){ if(L<=l&&r<=R){ return sum[b]-sum[a]; } int ans=0; int mid=(l+r)>>1; if(mid>=L) ans+=query(ls[a], ls[b], l, mid, L, R); if(mid<R) ans+=query(rs[a], rs[b], mid+1, r, L, R); return ans; } int main() { int T; cin>>T; while(T--){ cnt=0; tree[0]=ls[0]=rs[0]=sum[0]=0; scanf("%s",s); int len=manacher(); m=len/2; ll ans=0; for(int i=1;i<m;i++) { int L=i-p[i*2]/2+1; if(L!=i) update(L,tree[i-1],tree[i],1,m); else tree[i]=tree[i-1]; } for(int i=1;i<m;i++){ int R=i+p[i*2]/2-1; int t=query(tree[i], tree[R], 1, m, 1, i); ans+=t; } printf("%lld\n",ans); } }
但是我的板子一直过不了，一直TLE，借用了以为其他人的主席树板子才能过，好迷啊。
借用模版：https://blog.csdn.net/know_heng/article/details/78590061
待更新：树状数组离线做法