记录编号	284169	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]品酒大会	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	1.933 s
提交时间	2016-07-17 13:10:26	内存使用	106.17 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=600010;
const long long INF=1LL<<60;
int n,cnt,last,ord[maxn],c[maxn];
int fa[maxn],ch[maxn][26],len[maxn];
long long tmp[maxn],mx[maxn],mn[maxn],w[maxn];
long long num[maxn],tot[maxn],t1[maxn],t2[maxn];
char s[maxn];

struct SAM{
	SAM(){cnt=last=1;}
	void Insert(int c,int t){
		int p=last,np=last=++cnt;tmp[np]=1;
		len[np]=len[p]+1;mx[cnt]=mn[cnt]=w[t];
		while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
		if(!p)fa[np]=1;
		else{
			int q=ch[p][c],nq;
			if(len[q]==len[p]+1)
				fa[np]=q;
			else{
				len[nq=++cnt]=len[p]+1;
				mx[cnt]=-INF;mn[cnt]=INF;
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];
			}
		}
		return; 
	}
	
	void Solve(){
		for(int i=1;i<=cnt;i++)c[len[i]]++;
		for(int i=1;i<=len[last];i++)c[i]+=c[i-1];
		for(int i=1;i<=cnt;i++)ord[c[len[i]]--]=i;
		for(int i=1;i<=cnt;i++)t2[i]=num[i]=-INF;
		mn[1]=INF;mx[1]=-INF;
		
		for(int i=cnt;i>=1;i--){
			int p=ord[i];
			t1[fa[p]]+=tmp[fa[p]]*tmp[p];
			tmp[fa[p]]+=tmp[p];
			if(mn[fa[p]]!= INF)t2[fa[p]]=max(t2[fa[p]],mn[p]*mn[fa[p]]);
			if(mx[fa[p]]!=-INF)t2[fa[p]]=max(t2[fa[p]],mx[p]*mx[fa[p]]);
			mn[fa[p]]=min(mn[fa[p]],mn[p]);
			mx[fa[p]]=max(mx[fa[p]],mx[p]);
		}
		
		for(int i=1;i<=cnt;i++){
			tot[len[i]]+=t1[i];
			num[len[i]]=max(num[len[i]],t2[i]);
		}
		
		for(int i=n-2;i>=0;i--){
			tot[i]+=tot[i+1];
			num[i]=max(num[i],num[i+1]);
		}
		
		for(int i=0;i<n;i++)
			printf("%lld %lld\n",tot[i],tot[i]?num[i]:0);
	}
}sam;

int main(){
	freopen("savour.in","r",stdin);
	freopen("savour.out","w",stdout);
	scanf("%d%s",&n,s);
	for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
	for(int i=n;i;i--)sam.Insert(s[i-1]-'a',i);
	sam.Solve();	
	return 0;
}