记录编号	220553	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]品酒大会	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	9.663 s
提交时间	2016-01-19 07:53:22	内存使用	178.12 MiB

#define LL long long
#define lson l,mid,t
#define rson mid+1,r,t|1

#include<cstdio>
#include<cstring>

using namespace std;

char s[300010];
int n,first[1000010],sum,now;LL u=2;
const LL inf=(LL)(1LL<<60LL);LL val[300010];

//struct Suffix_Automaton{
	int root,last,tot,posl,posr;
	LL maxl[1200010],Ans1[300010],Ans2[300010];
	LL Max1,Max2,Min1,Min2,tree[1200010],mark[1200010],data;	
	struct Node{
		LL max1,min1,max2,min2;
		int par,go[26],len,cnt;
	}a[1000010];
	struct Edge{
		int v,next;
	}edge[1000010];
	inline LL Max(LL a,LL b){
		return a>b?a:b;
	}
	inline LL Min(LL a,LL b){
		return a<b?a:b;
	}
	inline void Add(int u,int v){
		edge[++sum].v=v;
		edge[sum].next=first[u];
		first[u]=sum;
	}
	inline void init(){
		root=last=tot=0;
		memset(a,0,sizeof(a));
		memset(first,0,sizeof(first));
		a[root].max1=a[root].max2=-inf;
		a[root].min1=a[root].min2=inf;
		for(int i=1,r=4*n;i<=r;i++)
			maxl[i]=-inf;
	}
	inline void extend(int x){
		int p,np=++tot,q,nq,w=s[x]-'a';
		a[np].len=a[last].len+1;
		a[np].cnt=1;
		a[np].max1=val[x];
		a[np].max2=-inf;
		a[np].min1=val[x];
		a[np].min2=inf;
		for(p=last;p&&(!a[p].go[w]);p=a[p].par)
			a[p].go[w]=np;
		if(!a[p].go[w])
			a[p].go[w]=np;
		else{
			q=a[p].go[w];
			if(a[q].len==a[p].len+1)
				a[np].par=q;
			else{
				a[nq=++tot]=a[q];
				a[nq].cnt=0;
				a[nq].max1=a[nq].max2=-inf;
				a[nq].min1=a[nq].min2=inf;
				a[q].par=a[np].par=nq;
				a[nq].len=a[p].len+1;
				for(;a[p].go[w]==q;p=a[p].par)
					a[p].go[w]=nq;
			}
		}
		last=np;
	}
	inline void Pushup(int rt){
		tree[rt]=tree[rt<<1]+tree[rt<<1|1];
	}
	inline void Clear(int l,int r,int rt){
		int t=rt<<1;
		if(l!=r){
			if(maxl[rt]>maxl[t])maxl[t]=maxl[rt];
			if(maxl[rt]>maxl[t|1])maxl[t|1]=maxl[rt];	
		}
		else return;
		if(mark[rt]!=0){
			int mid=(l+r)>>1;
			tree[t]+=mark[rt]*(mid-l+1);
			tree[t|1]+=mark[rt]*(r-mid);
			mark[t]+=mark[rt];
			mark[t|1]+=mark[rt];
			mark[rt]=0;
		}
	}
	inline void Modify(int l,int r,int rt){
		if(posl<=l&&posr>=r){
			tree[rt]+=data*(r-l+1);
			mark[rt]+=data;
			if(maxl[rt]<Max(Max1,Max2))
				maxl[rt]=Max(Max1,Max2);
			return;
		}
		Clear(l,r,rt);
		int mid=(l+r)>>1,t=rt<<1;
		if(posl<=mid)Modify(lson);
		if(posr>mid)Modify(rson);
		Pushup(rt);
	}
	inline void Query(int l,int r,int rt){
		if(l==r){
			Ans1[now]=tree[rt];
			Ans2[now]=maxl[rt];
			now++;return;
		}
		Clear(l,r,rt);
		int mid=(l+r)>>1,t=rt<<1;
		Query(lson);Query(rson);
	}
	inline void dfs(int rt){
		for(int i=first[rt];i>0;i=edge[i].next){
			dfs(edge[i].v);
			a[rt].cnt+=a[edge[i].v].cnt;
			if(a[edge[i].v].max1>a[rt].max1){
				a[rt].max2=Max(a[rt].max1,a[edge[i].v].max2);
				a[rt].max1=a[edge[i].v].max1;
			}
			else{
				if(a[edge[i].v].max1>a[rt].max2)
					a[rt].max2=a[edge[i].v].max1;
			}
			if(a[edge[i].v].min1<a[rt].min1){
				a[rt].min2=Min(a[rt].min1,a[edge[i].v].min2);
				a[rt].min1=a[edge[i].v].min1;
			}
			else{
				if(a[edge[i].v].min1<a[rt].min2)
					a[rt].min2=a[edge[i].v].min1;
			}
		}
		data=(LL)(a[rt].cnt)*(LL)(a[rt].cnt-1)/u;
		posl=a[a[rt].par].len+2;posr=a[rt].len+1;
		if(posl>posr)posl=posr;
		Max1=Max2=-inf;
		if(a[rt].max1!=-inf&&a[rt].max2!=-inf)
			Max1=a[rt].max1*a[rt].max2;
		if(a[rt].min1!=inf&&a[rt].min2!=inf)
			Max2=a[rt].min1*a[rt].min2;
		Modify(1,n,1);
	}
	inline void solve(){
		freopen("savour.in","r",stdin);
		freopen("savour.out","w",stdout);
		scanf("%d%s",&n,s+1);
		for(int i=1;i<=n;i++)
			scanf("%lld",&val[i]);	
		init();
		for(int i=n;i>=1;i--)
			extend(i);
		for(int i=1;i<=tot;i++)
			Add(a[i].par,i);
		dfs(0);now=0;
		Query(1,n,1);
		for(int i=0;i<n;i++){
			printf("%lld ",Ans1[i]);
			if(Ans1[i]==0)Ans2[i]=0;
			printf("%lld\n",Ans2[i]);
		}
	}
//}SAM;

int main()
{
	solve();
}