题意:给你一个字符串,问你满足s[i]=s[2n-i]=s[2n+i-2]的子串(这子串长度为3n-2)有多少个,原字符串长度<=5e5
题解:对于这种子串,其实要满足2个回文,跑过一次Manacher后,len[i]表示以i向两边扩展最远的回文串长度,
那么对于答案,实际就是统计满足下列条件(i,j)的对数
i <= j
j - i <= len[i]
j - i <= len[j]
移项就是
i >= j - len[j]
j <= i + len[i]
那么相当于,枚举i,询问(i,i+len[i])区间内,有多少个数(这里指权值 j - len[j])小于等于i
就是问区间内小于某个数的个数,那就是主席树裸题(好像其他人都写的树状树状ORZ)
#include<bits/stdc++.h>
#define N 500505
using namespace std;
int sum[N*],rt[N*],lc[N*],rc[N*];
int a[N],b[N],len[N],p,node_cnt,cnt,value[N];
char s[N];
void build(int &t,int l, int r)
{
t=++node_cnt;
sum[t]=;
if (l==r) return;
int mid=(l+r)>>;
build(lc[t],l,mid);
build(rc[t],mid+,r);
}
int modify(int o,int l,int r)
{
int oo = ++node_cnt;
lc[oo]=lc[o]; rc[oo]=rc[o]; sum[oo]=sum[o]+;
if (l==r) return oo;
int mid=(l+r)>>;
if (p<=mid) lc[oo]=modify(lc[oo],l,mid);
else rc[oo]=modify(rc[oo],mid+,r);
return oo;
}
int query(int u,int v,int l,int r,int k)
{
int ans,mid=((l+r)>>);
if (r<=k) return sum[v]-sum[u];
if (l>k) return ;
ans=query(lc[u],lc[v],l,mid,k);
if (mid<k) ans=ans+query(rc[u],rc[v],mid+,r,k);
return ans;
}
void manacher()
{
int pos=,R=;
for (int i=;i<=cnt;i++)
{
if (i<R) len[i]=min(len[*pos-i],R-i); else len[i]=;
while (<=i-len[i]&&i+len[i]<=cnt&&s[i-len[i]]==s[i+len[i]]) len[i]++;
if (i+len[i]>R) {pos=i;R=i+len[i];}
}
for(int i=;i<=cnt;i++)
{
a[i]=i-len[i]+;
b[i]=a[i];
}
}
int main()
{
int k, n, q, nn, v, l, r, x,T;
scanf("%d\n",&T);
while (T--)
{
scanf("%s",s+);
cnt=strlen(s+);
manacher();
sort(b+,b++cnt);
nn=unique(b+,b+cnt+)-b-;
node_cnt=;
build(rt[],,nn);
for (int i=;i<=cnt;i++)
{
p=lower_bound(b+,b+nn+,a[i])-b;
rt[i]=modify(rt[i-],,nn);
}
long long ans=;
for (int i=;i<=cnt;i++)
{
x=lower_bound(b+,b+nn+,i)-b;
if (x==nn+) x--;
if (b[x]>i) x--;
if(x==) continue;
if(min(len[i]+i-,cnt)<i+) continue;
ans=ans+query(rt[i],rt[min(len[i]+i-,cnt)],,nn,x);
}
printf("%lld\n",ans);
}
}