【算法】双端插入回文树（HDU5421）——litble

记两个 last 然后分别维护。

注意一下当整个字符串变成一个回文串时，两个 last 应该指向同一个节点。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
const int N=200005;
int las1,las2,SZ,m,l,r;LL ans;
int ch[N][26],fail[N],s[N],dep[N],len[N];
void init() {
    for(RI i=0;i<N;++i) s[i]=-1;
    SZ=1,las1=las2=0,l=100000,r=l-1,ans=0;
    fail[0]=1,fail[1]=0,len[0]=0,len[1]=-1;
    for(RI i=0;i<26;++i) ch[0][i]=ch[1][i]=0;
}
int find(int x,int kn,int fh) {
    while(s[kn-fh*len[x]-fh]!=s[kn]) x=fail[x];
    return x;
}
void ins(int t,int &last,int &kn,int fh) {
    kn+=fh,s[kn]=t;int now=find(last,kn,fh);
    if(!ch[now][t]) {
        ++SZ,fail[SZ]=ch[find(fail[now],kn,fh)][t];
        ch[now][t]=SZ,len[SZ]=len[now]+2,dep[SZ]=dep[fail[SZ]]+1;
        for(RI i=0;i<26;++i) ch[SZ][i]=0;
    }
    last=ch[now][t],ans+=dep[last];
    if(len[last]==r-l+1) las1=las2=last;//!!!!
}
int main()
{
    while(~scanf("%d",&m)) {
        int op;char ch[10];
        init();
        while(m--) {
            scanf("%d",&op);
            if(op==1) scanf("%s",ch),ins(ch[0]-'a',las1,l,-1);
            else if(op==2) scanf("%s",ch),ins(ch[0]-'a',las2,r,1);
            else if(op==3) printf("%d\n",SZ-1);
            else printf("%lld\n",ans);
        }
    }
    return 0;
}