题意：对一个字符串支持四种操作，前插入字符，后插入字符，询问本质不同的回文串数量和所有回文串的数量。
思路：
就是在普通回文树的基础上，维护suf（最长回文后缀）的同时再维护一个pre（最长回文前缀），即可完成以上操作。
代码基本是学习巨佬yyb的
#pragma GCC optimize (2) #pragma G++ optimize (2) #pragma comment(linker, "/STACK:102400000,102400000") #include<bits/stdc++.h> #include<cstdio> #include<vector> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,b,a) for(int i=b;i>=a;i--) #define clr(a,b) memset(a,b,sizeof(a)) #define pb push_back #define pii pair<int,int > using namespace std; typedef long long ll; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=300010; int size[maxn]; char s[maxn]; int l,r,pre,suf,n; ll ans; struct Palindromic_Tree { struct Node { int son[26]; int ff,len,dep; }t[maxn]; int last,tot; void init() { l=1e5,r=l-1; tot=0; clr(s,'\0'); clr(t,0); t[++tot].len=-1; t[0].ff=t[1].ff=1; } void extend(int c,int n,int &last,int op) { int p=last; while(s[n-op*t[p].len-op]!=s[n])p=t[p].ff; if(!t[p].son[c]) { int v=++tot,k=t[p].ff; t[v].len=t[p].len+2; while(s[n-op*t[k].len-op]!=s[n])k=t[k].ff; t[v].ff=t[k].son[c]; t[p].son[c]=v; t[v].dep=t[t[v].ff].dep+1; } last=t[p].son[c]; ans+=t[last].dep; if(t[last].len==r-l+1)pre=suf=last; } }a; int main(){ while(cin>>n){ a.init(); ans=0; while(n--){ int op=rd(); if(op<=2){ char c=getchar(); if(op==1)s[--l]=c,a.extend(c-97,l,pre,-1); else s[++r]=c,a.extend(c-97,r,suf,1); }else if(op==3)printf("%d\n",a.tot-1); else printf("%lld\n",ans); } } }