hdu5421 Victor and String 回文树（前后插入）

题目传送门

题意：对一个字符串支持四种操作，前插入字符，后插入字符，询问本质不同的回文串数量和所有回文串的数量。

思路：

　　就是在普通回文树的基础上，维护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=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

int size[maxn];

char s[maxn];

int l,r,pre,suf,n;

ll ans;

struct Palindromic_Tree

{

    struct Node

    {

        int son[];

        int ff,len,dep;

    }t[maxn];

    int last,tot;

    void init()

    {

        l=1e5,r=l-;

        tot=;

        clr(s,'\0');

        clr(t,);

        t[++tot].len=-;

        t[].ff=t[].ff=;

    }

    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+;

            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+;

        }

        last=t[p].son[c];

        ans+=t[last].dep;

        if(t[last].len==r-l+)pre=suf=last;

    }

}a;

int main(){

    while(cin>>n){

        a.init();

        ans=;

        while(n--){

            int op=rd();

            if(op<=){

                char c=getchar();

                if(op==)s[--l]=c,a.extend(c-,l,pre,-);

                else s[++r]=c,a.extend(c-,r,suf,);

            }else if(op==)printf("%d\n",a.tot-);

            else printf("%lld\n",ans);

        }

    }

}