记录编号	338355	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 生成魔咒	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.355 s
提交时间	2016-11-05 10:10:25	内存使用	8.70 MiB

#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int N=200010;
int n,s[N],par[N],len[N],root,last,top;
long long cnt[N],ans;
//cnt[i]表示能到达i的字符串个数 
map<int,int> go[N];
int New(int val=0){len[++top]=val;return top;}
void extend(int w){
	int p=last,np=New(len[p]+1);
	while (p&&!go[p][w]){
		go[p][w]=np;
		ans+=cnt[p];
		cnt[np]+=cnt[p];
		p=par[p];
	}
	if (!p) par[np]=root;
	else{
		int q=go[p][w];
		if (len[q]==len[p]+1) par[np]=q;
		else{
			int nq=New(len[p]+1);
			go[nq]=go[q];
			par[nq]=par[q];
			par[q]=par[np]=nq;
			while (p&&go[p][w]==q){
				go[p][w]=nq;
				cnt[q]-=cnt[p];
				cnt[nq]+=cnt[p];
				p=par[p];
			}
		}
	}
	last=np;
}
int main()
{
	freopen("menci_incantation.in","r",stdin);
	freopen("menci_incantation.out","w",stdout);
	scanf("%d",&n);
	root=last=New(0);
	cnt[root]=1;
	for (int i=1;i<=n;i++){
		scanf("%d",&s[i]);
		extend(s[i]);
		printf("%lld\n",ans);
	}
	return 0;
}