JZOJ 4427 Alphadog

看到在线插入字符维护答案，显然回文自动机啊（

新插入字符时，考虑答案增量。
即在插入第 i 个字符时考虑 i∑j=1LCP(j,i)。

易知 LCP(x,y) 相当于 S1…x 的最长回文后缀和 S1…y 的最长回文后缀在 PAM 上对应的状态在 Fail 树上的 LCA 对应的字符串长度。
于是就是一个经典套路……只不过要动态加点，所以上 LCT 即可。

代码：

#include <cstdio>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 1e5;
int n,op,s[N + 5];
long long ans;
namespace LCT
{
    #define chk(p) (tr[tr[p].fa].ch[1] == (p))
    #define isson(p) (tr[tr[p].fa].ch[0] == (p) || tr[tr[p].fa].ch[1] == (p))
    struct node
    {
        int fa;
        long long val,sum;
        long long Val,Sum;
        int add;
        int ch[2];
    } tr[N + 5];
    inline void up(int p)
    {
        tr[p].sum = tr[tr[p].ch[0]].sum + tr[p].val + tr[tr[p].ch[1]].sum,
        tr[p].Sum = tr[tr[p].ch[0]].Sum + tr[p].Val + tr[tr[p].ch[1]].Sum;
    }
    inline void push_add(int p,int k)
    {
        if(k)
            tr[p].add += k,
            tr[p].val += k * tr[p].Val,
            tr[p].sum += k * tr[p].Sum;
    }
    inline void down(int p)
    {
        if(tr[p].add)
            tr[p].ch[0] && (push_add(tr[p].ch[0],tr[p].add),1),
            tr[p].ch[1] && (push_add(tr[p].ch[1],tr[p].add),1),
            tr[p].add = 0;
    }
    inline void rotate(int p)
    {
        int x = tr[p].fa,y = tr[x].fa,d = chk(p),t = tr[p].ch[d ^ 1];
        isson(x) && (tr[y].ch[chk(x)] = p,1),
        tr[p].ch[d ^ 1] = x,tr[x].ch[d] = t,
        t && (tr[t].fa = x),
        tr[x].fa = p,tr[p].fa = y,
        up(x),up(p);
    }
    inline void splay(int p)
    {
        static int st[N + 5];
        int top = 0;
        st[++top] = p;
        int x = p;
        for(;isson(x);st[++top] = x = tr[x].fa);
        for(;top;down(st[top--]));
        for(;isson(p);rotate(p))
        {
            x = tr[p].fa;
            isson(x) && (rotate(chk(p) ^ chk(x) ? p : x),1);
        }
    }
    inline void access(int p)
    {
        for(register int x = 0;p;p = tr[x = p].fa)
            splay(p),tr[p].ch[1] = x,up(p);
    }
}
namespace PAM
{
    struct node
    {
        int ch[26];
        int fa,len;
    } pam[N + 5];
    int las = 1,tot = 1;
    inline int init()
    {
        pam[1].len = -1,pam[0].fa = 1;
        return 0;
    }
    int Init = init();
    void insert(int *s,int i)
    {
        int cur = las,x = s[i];
        for(;s[i - pam[cur].len - 1] ^ s[i];cur = pam[cur].fa);
        if(!pam[cur].ch[x])
        {
            int p = ++tot,q = pam[cur].fa;
            pam[p].len = pam[cur].len + 2;
            for(;s[i - pam[q].len - 1] ^ s[i];q = pam[q].fa);
            pam[p].fa = pam[q].ch[x],
            pam[cur].ch[x] = p,
            LCT::tr[p].fa = pam[p].fa ? pam[p].fa : 1,
            LCT::tr[p].Val = LCT::tr[p].Sum = pam[p].len - pam[pam[p].fa].len;
        }
        las = pam[cur].ch[x],
        LCT::access(las),LCT::splay(las),LCT::push_add(las,1),ans += LCT::tr[las].sum;
    }
}
int main()
{
    read(n),read(op),s[0] = -1;
    long long x;
    for(register int i = 1;i <= n;++i)
        read(x),op && (x ^= ans),s[i] = x,PAM::insert(s,i),printf("%lld\n",ans);
}