由于后缀自动机的构造本来就是一个在线的过程，所以我们可以考虑每次往答案中添加新的贡献。
又根据后缀自动机的定义，不同子串的个数其实就是 \(\sum\limits_{i = 1}^{tot} len_i - len_{fa_i}\)。
所以我们再每次添加字符的时候更新答案即可。
这题如果用 SA 来做的话会很麻烦，但是 SAM 就很简洁了。
代码： 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
using namespace std;
using namespace tr1;
const int N = 1e5;
int n;
int a[N + 5];
unordered_map<int,int> hs;
int cnt;
struct node
{
unordered_map<int,int> ch;
int fa,len;
} sam[(N << 1) + 5];
long long ans;
int whole = 1,tot = 1;
void push(int x)
{
int cur = whole,p = whole = ++tot;
sam[p].len = sam[cur].len + 1;
for(;cur && !sam[cur].ch.count(x);cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
int nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
for(;cur && sam[cur].ch.count(x) && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
ans += sam[p].len - sam[sam[p].fa].len;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),a[i] = hs.count(a[i]) ? hs[a[i]] : (hs[a[i]] = ++cnt),push(a[i]),printf("%lld\n",ans);
}