记录编号	249133	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 生成魔咒	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.621 s
提交时间	2016-04-12 09:57:14	内存使用	111.33 MiB

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=150010;
const int maxb=50;
const int mod=41;
int n; LL ans=0;

inline int read(){
	int ret=0; char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar())
	ret=ret*10+ch-'0'; return ret;
}

struct hashset{
	int next[maxb],val[maxb],As[maxb];
	int h[mod],tot;
	void init(){
		tot=0; memset(h,0,sizeof(h));
	}
	void push(int x,int id){
		int now=x%mod; if (now<0) now+=mod;
		for (int i=h[now];i;i=next[i])
		    if (val[i]==x) return;
		++tot; next[tot]=h[now]; h[now]=tot;
		val[tot]=x; As[tot]=id; return;
	}
	int find(int x){
		int now=x%mod; if (now<0) now+=mod;
		for (int i=h[now];i;i=next[i])
		    if (val[i]==x) return As[i];
		return -1;
	}
	void repush(int x,int id){
		int now=x%mod; if (now<0) now+=mod;
		for (int i=h[now];i;i=next[i])
		    if (val[i]==x){As[i]=id;return;}
	}
}son[maxn];

struct suffix_automation{
	int fa[maxn];
	int l[maxn],last,tot,root;
	void init(){
		tot=0; last=root=++tot;
	}
	int add(int x){
		int p=last,np=++tot; last=np; l[np]=l[p]+1; 
		while (p&&son[p].find(x)==-1) son[p].push(x,np),p=fa[p];
		if (!p) fa[np]=root;
		else{
			int q=son[p].find(x);
			if (l[q]==l[p]+1) fa[np]=q;
			else{
				int nq=++tot; fa[nq]=fa[q]; l[nq]=l[p]+1;
				for (int i=1;i<=son[q].tot;++i){
					son[nq].next[i]=son[q].next[i];
					son[nq].As[i]=son[q].As[i];
					son[nq].val[i]=son[q].val[i];
				}
				for (int i=0;i<mod;++i) son[nq].h[i]=son[q].h[i];
				son[nq].tot=son[q].tot; fa[q]=fa[np]=nq;
				while (son[p].find(x)==q) son[p].repush(x,nq),p=fa[p];
			}
		}return l[np]-l[fa[np]];
	}
}sam;

int main(){
	freopen("menci_incantation.in","r",stdin);
	freopen("menci_incantation.out","w",stdout);
	sam.init();
	scanf("%d",&n); int x;
	for (int i=1;i<=n;++i)
	    printf("%lld\n",ans+=sam.add(x=read()));
}