Description：

每次在当前串的末尾加一个字符，询问本质不同的子串数量。

$1\leqslant n\leqslant 10^5,1\leqslant s_i\leqslant 10^9$

Solution：

发现其实在最后加一个新字符会产生以这个位置为后缀的很多新子串，但是有些已经计算过了，由于后缀自动机中 $par$ 表示的是最长的另一个状态是他的一些后缀，所以这次的贡献就是 $s[np].maxl-s[s[np].par].maxl$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 100010

struct node

{

	int par,maxl;

	map<int,int> tr;

}s[MAXN << 1];

int ptr = 1,root = 1,last = 1;

int newnode(int x){int k = ++ptr;s[k].maxl = x;return k;}

long long ans = 0;

void extend(int k)

{

	int p = last;

	int np = newnode(s[p].maxl + 1);

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			s[nq].tr = s[q].tr;

			s[nq].par = s[q].par;

			s[q].par = s[np].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	last = np;

	ans += s[np].maxl - s[s[np].par].maxl;

	printf("%lld\n",ans);

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)extend(rd());

	return 0;

}