看到在线插入字符维护答案，显然回文自动机啊（
新插入字符时，考虑答案增量。
即在插入第 \(i\) 个字符时考虑 \(\sum\limits_{j=1}^i {\rm LCP}(j,i)\)。
易知 \({\rm LCP}(x,y)\) 相当于 \(S_{1\dots x}\) 的最长回文后缀和 \(S_{1\dots y}\) 的最长回文后缀在 PAM 上对应的状态在 Fail 树上的 LCA 对应的字符串长度。
于是就是一个经典套路……只不过要动态加点，所以上 LCT 即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
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
{
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);
}