[hihocoder1783] Another Duplicate Counting
/ / 阅读耗时 9 分钟 题目链接。爆肝几小时AC(菜。
题意很明确，给定一个长度为$n$的字符串$S$，求：
其中$f(S)$是$S$中本质不同的回文串数量。
考虑以$i$为结尾的若干回文串，计算它们对答案的贡献。对于回文串$S$，假设它上一次出现的末尾位置为$a,(a<i)$，它的长度为$l$，那么它参与的答案区间的左端点区间是$[a-l+2,i-l+1]$，右端点区间为$[i,n]$。
所以它对答案的贡献是：
拿等差数列求和公式计算可得：
对于若干回文串$S$，在位置$i$的答案总贡献当然是：
记回文串有$N$个，那么展开这个多项式，可以得到：
从上式中可以发现我们需要维护五个量（包括回文串数量$N$）。
现在我们需要快速地得到有哪些回文串在$i$上结尾，并且维护这五个量。回文自动机可以很好地解决这个问题，对于位置$i$，这些回文串必然有着回文后缀的关系，它们都在一条树链上，于是问题转化为维护树链上的量，有很多方法可以解决这个问题。
注意到回文树是动态构建并且动态维护的，所以树链剖分不能使用。对于动态的树链维护问题，可以选择LCT。
于是本题可以使用LCT维护回文树的方法在$O(nlogn)$时间复杂度内解决。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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
using namespace std;
typedef long long ll;
struct Node
{
int len, fa, ch[26], la;
} nd[N << 1];
int ct = 1, last, k;
char op[N];
namespace LCT {
int son[N][2], fa[N], lazy[N], sta[N], lazy2[N];
ll len[N], la[N], lalen[N], la2[N], num[N];
inline void init(int x)
{
son[x][0] = son[x][1] = fa[x] = lazy[x] = lazy2[x] = 0;
len[x] = nd[x].len, la[x] = nd[x].la, la2[x] = 1ll * nd[x].la * nd[x].la;
lalen[x] = 1ll * nd[x].la * nd[x].len, num[x] = 1;
}
inline void update(int x)
{
len[x] = len[son[x][0]] + len[son[x][1]] + nd[x].len;
la[x] = la[son[x][0]] + la[son[x][1]] + nd[x].la;
lalen[x] = lalen[son[x][0]] + lalen[son[x][1]] + 1ll * nd[x].la * nd[x].len;
la2[x] = la2[son[x][0]] + la2[son[x][1]] + 1ll * nd[x].la * nd[x].la;
num[x] = num[son[x][0]] + num[son[x][1]] + 1;
}
inline bool isNotRoot(int x)
{
return son[fa[x]][0] == x || son[fa[x]][1] == x;
}
inline int identify(int x)
{
return son[fa[x]][1] == x;
}
inline void change(int f, int s, int w)
{
fa[s] = f, son[f][w] = s;
}
inline void rotate(int x)
{
int f = fa[x], g = fa[f], i = identify(x), j = identify(f);
if (!isNotRoot(f))
fa[x] = g;
else
change(g, x, j);
change(f, son[x][i ^ 1], i), change(x, f, i ^ 1);
update(f), update(x);
}
inline void pushr(int x)
{
swap(son[x][0], son[x][1]), lazy[x] ^= 1;
}
inline void pushr2(int x, int to)
{
la[x] = num[x] * to;
lalen[x] = len[x] * to;
la2[x] = 1ll * to * to * num[x];
nd[x].la = to;
lazy2[x] = to;
}
inline void pushdown(int x)
{
if (lazy[x]) pushr(son[x][0]), pushr(son[x][1]), lazy[x] = 0;
if (lazy2[x]) pushr2(son[x][0], lazy2[x]), pushr2(son[x][1], lazy2[x]), lazy2[x] = 0;
}
inline void splay(int x)
{
int i = 0, y = x;
sta[++i] = y;
while (isNotRoot(y)) sta[++i] = y = fa[y];
while (i) pushdown(sta[i--]);
while (isNotRoot(x)) {
int f = fa[x];
if (isNotRoot(f)) {
if (identify(x) == identify(f))
rotate(f);
else
rotate(x);
}
rotate(x);
}
}
inline void access(int x)
{
for (int i = 0; x; x = fa[i = x]) splay(x), son[x][1] = i, update(x);
}
inline void makeRoot(int x)
{
access(x), splay(x), pushr(x);
}
inline int findRoot(int x)
{
access(x), splay(x);
while (son[x][0]) pushdown(x), x = son[x][0];
splay(x);
return x;
}
inline void link(int x, int y)
{
if (y == 0) y = 1;
makeRoot(x);
if (x != findRoot(y)) fa[x] = y;
}
inline void cut(int x, int y)
{
makeRoot(x);
if (findRoot(y) == x && fa[y] == x && !son[y][0]) fa[y] = 0, son[x][1] = 0, update(x);
}
inline void split(int x, int y)
{
makeRoot(x), access(y), splay(y);
}
}; // namespace LCT
inline int newNode(int x)
{
int p = ++ct;
nd[p].len = x, nd[p].la = x - 1, nd[p].fa = 0, LCT::init(p);
for (int i = 0; i < 26; i++) nd[p].ch[i] = 0;
return p;
}
inline void add(int c, int pos)
{
int u = last;
while (op[pos - nd[u].len - 1] != op[pos]) u = nd[u].fa;
if (nd[u].ch[c] == 0) {
int s = newNode(nd[u].len + 2), f = nd[u].fa;
while (op[pos - nd[f].len - 1] != op[pos]) f = nd[f].fa;
nd[s].fa = nd[f].ch[c], LCT::link(s, nd[s].fa), nd[u].ch[c] = s;
}
last = nd[u].ch[c];
}
int main()
{
int T;
scanf("%d", &T);
for (int TT = 1; TT <= T; TT++) {
nd[0].len = 0, nd[0].fa = 1, nd[0].la = 0, nd[1].len = -1, nd[1].fa = 0, nd[1].la = 0;
for (int i = 0; i < 26; i++) nd[0].ch[i] = nd[1].ch[i] = 0;
scanf("%s", op + 1);
ct = 1;
int n = strlen(op + 1);
for (int i = 1; i <= 2 * n; i++) LCT::init(i);
ll ans = 0;
for (int i = 1; i <= n; i++) {
add(op[i] - 'a', i);
LCT::split(1, last), LCT::splay(1);
ll num = LCT::num[1] - 1;
ll len = LCT::len[1] - nd[1].len;
ll la = LCT::la[1] - nd[1].la;
ll lalen = LCT::lalen[1] - 1ll * nd[1].la * nd[1].len;
ll la2 = LCT::la2[1] - 1ll * nd[1].la * nd[1].la;
ll tmpans = num * (1ll * i * n - i);
tmpans += 2ll * i * len;
tmpans += 1ll * (1 - i - n) * la;
tmpans -= 2ll * lalen;
tmpans += la2;
ans += 1ll * (n - i + 1) * tmpans / 2;
LCT::pushr2(1, i);
}
printf("Case #%d: %lld\n", TT, ans);
}
return 0;
}