本质不同子串数量等于所有点的len-parent树上父亲的len的和。可以直接维护。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define ll long long
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,fail[N],len[N],cnt=1,last=1;
ll ans;
map<int,int> son[N];
void relink(int x,int y)
{
ans+=len[fail[x]];
fail[x]=y;
ans-=len[fail[x]];
}
void ins(int c)
{
int x=++cnt,p=last;last=x;ans+=len[x]=len[p]+1;
while (son[p].find(c)==son[p].end()) son[p][c]=x,p=fail[p];
if (!p) relink(x,1);
else
{
int q=son[p][c];
if (len[p]+1==len[q]) relink(x,q);
else
{
int y=++cnt;
ans+=len[y]=len[p]+1;
son[y]=son[q];
relink(y,fail[q]);
relink(q,y);
relink(x,y);
while (son[p][c]==q) son[p][c]=y,p=fail[p];
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("qwq.in","r",stdin);
freopen("qwq.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=1;i<=n;i++)
{
ins(read());
printf(LL,ans);
}
return 0;
}