记录编号	393477	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 生成魔咒	最终得分	100
用户昵称	will	是否通过	通过
代码语言	C++	运行时间	0.165 s
提交时间	2017-04-11 13:52:05	内存使用	7.16 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN=100050, MAXB=2e6, INF=0x3f3f3f3f;
char buf[MAXB], *cp=buf;
void rd(int &x){
	x=0;
	while(*cp<'0'||'9'<*cp) cp++;
	while('0'<=*cp&&*cp<='9') x=x*10+*cp-'0', cp++;
}
int N, M, up;
int w[MAXN], rk[MAXN], ht[MAXN], sa[MAXN], c[MAXN];
struct Node{Node *fa; int mn;}nd[MAXN];
ll sum, ans[MAXN];
void init(){for(int i=0; i<=N; ++i) nd[i].fa=nd+i, nd[i].mn=ht[i];}
Node *find(Node *x){return x==x->fa?x:(x->fa=find(x->fa));}
void unite(Node *x, Node *y){
	x=find(x); y=find(y);
	x->fa=y;
	if(x->mn<y->mn) sum+=y->mn, y->mn=x->mn;
	else sum+=x->mn;
}
inline int wcmp(int *x, int a, int b, int k){
	return x[a]==x[b]&&x[a+k]==x[b+k];
}
inline void rsort(int *x, int *y){
	memset(c, 0, up*sizeof(int));
	for(int i=0; i<N; ++i) c[x[i]]++;
	for(int i=1; i<up; ++i) c[i]+=c[i-1];
	for(int i=N-1; i>=0; --i) sa[--c[x[y[i]]]]=y[i];
}
void getsa(){
	int *x=rk, *y=ht;
	for(int i=0; i<N; ++i) x[i]=w[i], y[i]=i;
	rsort(x,y);
	for(int k=1, p=0; p<N; k<<=1, up=p){
		p=0;
		for(int i=N-k; i<N; ++i) y[p++]=i;
		for(int i=0; i<N; ++i) if(sa[i]>=k) y[p++]=sa[i]-k;
		rsort(x,y); swap(x,y); p=0; x[sa[0]]=p++;
		for(int i=1; i<N; ++i)
			if(wcmp(y,sa[i],sa[i-1],k)) x[sa[i]]=p-1;
			else x[sa[i]]=p++;
	}
	for(int i=0; i<N; ++i) rk[sa[i]]=i;
	ht[0]=0;
	for(int i=0, j, p=0; i<N-1; ++i){
		for((p?p--:0),j=sa[rk[i]-1];w[i+p]==w[j+p];++p);
		ht[rk[i]]=p;
	}
}
int hc[MAXN], lc[MAXN], tp1[MAXN], tp2[MAXN];
int main(){
	FILE *fi=fopen("menci_incantation.in","r");
	buf[fread(buf, 1, MAXB, fi)]=0;
	freopen("menci_incantation.out","w",stdout);
	rd(N);
	for(int i=0; i<N; ++i) rd(c[i]);
	for(int i=0; i<N; ++i) lc[c[i]&0xffff]++, hc[c[i]>>16]++;
	for(int i=1; i<(1<<16); ++i) hc[i]+=hc[i-1], lc[i]+=lc[i-1];
	for(int i=N-1; i>=0; --i) tp1[--lc[c[i]&0xffff]]=i;
	for(int i=N-1; i>=0; --i) tp2[--hc[c[tp1[i]]>>16]]=tp1[i];
	w[N-tp2[0]-1]=1;
	for(int i=1, j=1; i<N; ++i) w[N-tp2[i]-1]=c[tp2[i]]==c[tp2[i-1]]?j:++j;
	M=N++; up=N+1; getsa();
	sum=(ll)M*(M+1)/2;
	for(int i=0; i<N; ++i) sum-=ht[i];
	ans[N]=sum; init();
	for(int i=0; i<M; ++i){
		sum-=M-i;
		unite(nd+rk[i],nd+rk[i]+1);
		ans[M-i]=sum;
	}
	for(int i=2; i<=N; ++i) printf("%lld\n", ans[i]);
	return 0;
}