记录编号	248786	评测结果	AAAAAAAAAA
题目名称	2223.[SDOI 2016 Round1] 生成魔咒	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.376 s
提交时间	2016-04-11 14:16:54	内存使用	6.41 MiB

#include<map>
#include<cstdio>

namespace Suffix_Automaton{
	#define maxn 100050
	#define ll long long
	int last,root,tot;ll res;
	struct Node{int len,par;std::map<int,int>go;}a[maxn<<1];
	void extend(int w){
		int p=last,np=++tot;
		a[np].len=a[last].len+1;
		while(p&&(!a[p].go.count(w)))a[p].go[w]=np,p=a[p].par;
		if(!a[p].go.count(w))a[p].go[w]=np;
		else{
			int q=a[p].go[w],nq;
			if(a[q].len==a[p].len+1)a[np].par=q;
			else{
				a[nq=++tot]=a[q];a[nq].len=a[p].len+1;
				a[q].par=a[np].par=nq;
				for(;a[p].go.count(w)&&a[p].go[w]==q;p=a[p].par)a[p].go[w]=nq;
			}
		}last=np;
		res+=a[last].len-a[a[last].par].len;
		printf("%lld\n",res);
	}
};

inline int in()
{
	int x=0;char c=getchar();
	while(c<'!')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3+x<<1)+c-'0',c=getchar();
	return x;
}

int main()
{
	freopen("menci_incantation.in","r",stdin);
	freopen("menci_incantation.out","w",stdout);
	using namespace Suffix_Automaton;
	int n;scanf("%d",&n);
	for(int i=1,p;i<=n;i++)
		p=in(),extend(p);
	return 0;
}