记录编号	389290	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 生成魔咒	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.229 s
提交时间	2017-03-31 07:20:27	内存使用	6.42 MiB

#include <stdio.h>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#define Mem(a, b) memset(a, b, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
#define RG register
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;
IL void qkin(RG int &res){
	RG int x,f=1; RG char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;}
IL void read(RG int &A){ qkin(A); }
IL void read(RG int &A,RG int &B){ qkin(A),qkin(B); }
IL void read(RG int &A,RG int &B,RG int &C){ qkin(A),qkin(B),qkin(C); }
#define Gets(s) scanf("%s", s+1);
const double INF = 1e60;
const int inf = 0x7f7f7f7f;
const double Pi = acos(-1);
const double eps = 1e-8;
const int maxn = 200010;
LL ans;
int n,cnt,last,rt;
struct SAM{
	int val, root; map<int,int> next;
}a[maxn];
void add(int c){
	int p = last, np = ++cnt;
	a[np].val = a[p].val + 1;
	while(p && !a[p].next[c]){
		a[p].next[c] = np;
		p = a[p].root;
	}
	if(!p) a[np].root = rt;
	else {
		int q = a[p].next[c];
		if(a[q].val == a[p].val + 1) a[np].root = q;
		else {
			int nq = ++cnt;
			a[nq] = a[q];
			a[nq].val = a[p].val + 1;
			a[np].root = a[q].root = nq;
			while(p && a[p].next[c] == q){
				a[p].next[c] = nq;
				p = a[p].root;
			}
		}
	}
	last = np;
	ans += a[np].val - a[a[np].root].val;
	printf("%lld\n", ans);
}
int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("menci_incantation.in", "r", stdin);
	freopen("menci_incantation.out", "w", stdout);
#endif
	read(n); last = rt = ++cnt;
	for(int i=1; i<=n; i++){
		int x; read(x); add(x);
	}
	return 0;
}