记录编号	389177	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]品酒大会	最终得分	100
用户昵称	wumingshi	是否通过	通过
代码语言	C++	运行时间	1.971 s
提交时间	2017-03-30 20:05:05	内存使用	23.47 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=300010;
struct edge
{
	int nxt,to;
}a[N];
ll ans[N],Max[N],Min[N],tot[N],size[N];
char s[N];
int t1[N],t2[N],sa[N],height[N],rank[N],c[N],f[N],head[N];
int n,num,lv;
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 x,int y)
{
	a[++num].nxt=head[x],a[num].to=y,head[x]=num;
}
int find(int n)
{
	if(f[n]!=n) f[n]=find(f[n]);
	return f[n];
}
inline bool cmp(int *y,int a,int b,int k)
{
	int r1=y[a],r2=y[b];
	int r3=a+k>=n?-1:y[a+k];
	int r4=b+k>=n?-1:y[b+k];
	return r1==r2&&r3==r4;
}
inline void makesa()
{
	int *x=t1,*y=t2,m=30;
	for(int i=0;i<m;i++) c[i]=0;
	for(int i=0;i<n;i++) c[x[i]=s[i]-'a']++;
	for(int i=1;i<m;i++) c[i]+=c[i-1];
	for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(int k=1;k<=n;k<<=1)
	{
		int 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;
		for(int i=0;i<m;i++) c[i]=0;
		for(int i=0;i<n;i++) c[x[y[i]]]++;
		for(int i=1;i<m;i++) c[i]+=c[i-1];
		for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1;x[sa[0]]=0;
		for(int i=1;i<n;i++)
		  x[sa[i]]=cmp(y,sa[i],sa[i-1],k)?p-1:p++;
		if(p>=n) break;
		m=p;
	}
}
inline void makeheight()
{
	for(int i=0;i<n;i++) rank[sa[i]]=i;
	int k=0;
	for(int i=0;i<n;i++)
	  if(rank[i])
	  {
	  	int j=sa[rank[i]-1];
	  	if(k) k--;
	  	while(s[i+k]==s[j+k]) k++;
	  	height[rank[i]]=k;
	  }
}
inline void merge(int i,int x,int y)
{
	f[y]=x;
	ans[i]=max(ans[i],Max[sa[x]]*Max[sa[y]]);
	ans[i]=max(ans[i],Min[sa[x]]*Min[sa[y]]);
	Max[sa[x]]=max(Max[sa[x]],Max[sa[y]]);
	Min[sa[x]]=min(Min[sa[x]],Min[sa[y]]);
	tot[i]+=size[sa[x]]*size[sa[y]];
	size[sa[x]]+=size[sa[y]];
}
inline void solve()
{
	for(int i=1;i<n;i++)
	  add(height[i],i);
	for(int i=n-1;i>=0;i--)
	  for(int j=head[i];j;j=a[j].nxt)
	  {
		int x=find(a[j].to),y=find(a[j].to-1);
		merge(i,x,y);
	  }
	for(int i=n-2;i>=0;i--)
	  tot[i]+=tot[i+1],ans[i]=max(ans[i],ans[i+1]);
	for(int i=0;i<n;i++)
	  if(tot[i]) printf("%lld %lld\n",tot[i],ans[i]);
	  else printf("0 0\n");
}
int main()
{
	freopen("savour.in","r",stdin);
	freopen("savour.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s);
	for(int i=0;i<n;i++)
	  scanf("%d",&lv),f[i]=i,Max[i]=Min[i]=lv,size[i]=1,ans[i]=-1e18;
	makesa();
	makeheight();
	solve();
	return 0;
}