记录编号	268958	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 生成魔咒	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.460 s
提交时间	2016-06-12 22:06:07	内存使用	6.42 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
const int maxn=200010;

int cnt,last;
long long ans;
int fa[maxn],len[maxn];
map<int,int>ch[maxn];

struct SAM{
	SAM(){
		cnt=0;
		last=++cnt;
		ans=0;
	}
	void Insert(int c){
		int p=last,np=last=++cnt;
		len[np]=len[p]+1;
		while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
		if(!p)fa[np]=1;
		else{
			int q=ch[p][c];
			if(len[p]+1==len[q])fa[np]=q;
			else{
				int nq=++cnt;
				len[nq]=len[p]+1;
				ch[nq]=ch[q];
				fa[nq]=fa[q];
				fa[q]=fa[np]=nq;
				while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];
			}
		}
		ans+=len[last]-len[fa[last]];
		printf("%lld\n",ans);
		return;
	}
}sam;
int main(){
#ifndef ONLINE_JUDGE
	freopen("menci_incantation.in","r",stdin);
	freopen("menci_incantation.out","w",stdout);
#endif
	int n;
	scanf("%d",&n);
	for(int i=1,a;i<=n;i++){
		scanf("%d",&a);
		sam.Insert(a);
	}
	return 0;
}