题意:给你一个字符串,问你满足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)

       

1 #include
     
       2 #define N 500505 3 using namespace std; 4 int sum[N*25],rt[N*25],lc[N*25],rc[N*25]; 5 int a[N],b[N],len[N],p,node_cnt,cnt,value[N]; 6 char s[N]; 7 void build(int &t,int l, int r) 8 { 9     t=++node_cnt;10     sum[t]=0;11     if (l==r) return;12     int mid=(l+r)>>1;13     build(lc[t],l,mid);14     build(rc[t],mid+1,r);15 }16 int modify(int o,int l,int r)17 {18     int oo = ++node_cnt;19     lc[oo]=lc[o]; rc[oo]=rc[o]; sum[oo]=sum[o]+1;20     if (l==r) return oo;21     int mid=(l+r)>>1;22     if (p<=mid) lc[oo]=modify(lc[oo],l,mid);23     else rc[oo]=modify(rc[oo],mid+1,r);24     return oo;25 }26 int query(int u,int v,int l,int r,int k)27 {28     int ans,mid=((l+r)>>1);29     if (r<=k) return sum[v]-sum[u];30     if (l>k) return 0;31     ans=query(lc[u],lc[v],l,mid,k);32     if (mid
      
       R) {pos=i;R=i+len[i];}43     }44     for(int i=1;i<=cnt;i++)45     {46         a[i]=i-len[i]+1;47         b[i]=a[i];48     }49 }50 int main() 51 {52     int k, n, q, nn, v, l, r, x,T;53     scanf("%d\n",&T);54     while (T--)55     {56         scanf("%s",s+1);57         cnt=strlen(s+1);58         manacher();59         sort(b+1,b+1+cnt);60         nn=unique(b+1,b+cnt+1)-b-1;61         node_cnt=0;62         build(rt[0],1,nn);63         for (int i=1;i<=cnt;i++)64         {65             p=lower_bound(b+1,b+nn+1,a[i])-b;66             rt[i]=modify(rt[i-1],1,nn);67         }68         long long ans=0;69         for (int i=1;i<=cnt;i++)70         {71             x=lower_bound(b+1,b+nn+1,i)-b;72             if (x==nn+1) x--;73             if (b[x]>i) x--;74             if(x==0) continue;75             if(min(len[i]+i-1,cnt)