首先有两个结论：
1.后缀自动机具有最简性，即每种不同的子串只会在sam上体现一次，体现形式是sam上一条由root出发的路径。
2.一个字符串不同子串的个数等于所有关键节点的max(x)-min(x)+1。证明就是考虑后缀自动机的最简性。
然后，这就是个水题了。
每次插入一个字符后，更新答案即可。
#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<algorithm>
#define N 330000
#define L 300000
#define eps 1e-7
#define inf 1e9+7
#define ll long long
using namespace std;
inline int read()
{
char ch=0;
int x=0,flag=1;
while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*flag;
}
char ch[N];
bool flag[N];
int root=1,size=1,last=1,id[N];
struct node{int len,link;map<int,int>nxt;}s[N];
void insert(int k)
{
int cur=++size,p=last;
s[cur].len=s[p].len+1;
while(p&&!s[p].nxt[k])
{
s[p].nxt[k]=cur;
p=s[p].link;
}
last=cur;
if(!p){s[cur].link=root;return;}
int q=s[p].nxt[k];
if(s[q].len==s[p].len+1)s[cur].link=q;
else
{
int clone=++size;
s[clone]=s[q];
s[clone].len=s[p].len+1;
while(p&&s[p].nxt[k]==q)
{
s[p].nxt[k]=clone;
p=s[p].link;
}
s[q].link=s[cur].link=clone;
}
}
int main()
{
ll ans=0;
int n=read();
for(int i=1;i<=n;i++)
{
int x=read();
insert(x);
ans+=s[last].len-s[s[last].link].len;
printf("%lld
",ans);
}
return 0;
}