[SDOI2016]生成魔咒

题目描述

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 $1,2$ 拼凑起来形成一个魔咒串 $[1,2]$。

一个魔咒串 $S$ 的非空字串被称为魔咒串 $S$ 的生成魔咒。

例如 $S=[1,2,1]$ 时，它的生成魔咒有 $[1],[2],[1,2],[2,1],[1,2,1]$ 五种。$S=[1,1,1]$ 时，它的生成魔咒有 $[1],[1,1],[1,1,1]$ 三种，最初 S 为空串。

共进行 $n$ 次操作，每次操作是在 $S$ 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 $S$ 共有多少种生成魔咒。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个数，第 $i$ 个数表示第 $i$ 次操作加入的魔咒字符 xix_ixi​。

输出格式

输出 $n$ 行，每行一个数。
第 $i$ 行的数表示第 $i$ 次操作后 $S$ 的生成魔咒数量

样例 #1

样例输入 #1

7
1 2 3 3 3 1 2

样例输出 #1

1
3
6
9
12
17
22

提示

数据规模与约定

对于 $10\%$ 的数据，保证 $1\le n\le 10$；
对于 $30\%$ 的数据，保证 $1\le n\le 100$；
对于 $60\%$ 的数据，保证 1≤n≤1031 \\le n \\le 10^31≤n≤103；
对于 $100\%$ 的数据，保证 1≤n≤1051 \\le n \\le 10^51≤n≤105，1≤xi≤1091 \\leq x_i \\leq 10^91≤xi​≤109。

题意：

给定 n 次插入字符串操作，要求求出每次插入一个字符时，当前字符串包含的本质不同子串的数量。

思路：

我们知道，后缀链接树上存储了一个字符串的所有子串，我们可以把当前的答案看做是树上所有节点包含的子串数量总和，树上每个节点 u 包含的子串数量为：len[u] - len[fa[u]]，当插入一个字符，给答案造成了贡献，我们等价地看成是新创建了个节点 np，这个操作对于答案的贡献为即为 len[np] - len[fa[np]]。

因此具体做法就是，每进行extend一个字符的时候，对于答案累加上应有的贡献即可。

时间复杂度：

$O(n)$

代码：

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = N << 1;
int n, fa[M], len[M], tot = 1, np = 1;
unordered_map<int, unordered_map<int, int>> ch;
vector<int> g[M];
string s;
ll sum = 0;void extend(int c)
{int p = np; np = ++tot;len[np] = len[p] + 1;while (p && !ch[p][c]) {ch[p][c] = np;p = fa[p];}if (!p) {fa[np] = 1;}else {int q = ch[p][c];if (len[q] == len[p] + 1) {fa[np] = q;}else {int nq = ++tot;len[nq] = len[p] + 1;fa[nq] = fa[q], fa[q] = fa[np] = nq;while (p && ch[p][c] == q) {ch[p][c] = nq;p = fa[p];}ch[nq] = ch[q];}}sum += (len[np] - len[fa[np]]);
}signed main()
{cin >> n;for (int i = 0; i < n; ++i) {int c; cin >> c;extend(c);printf("%lld\\n", sum);}return 0;
}