记录编号	220615	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]品酒大会	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	5.572 s
提交时间	2016-01-19 17:26:56	内存使用	106.35 MiB

#include<cstdio>
#include<cstring>
inline long long MAX(long long A,long long B){return A>B?A:B;}
int n,c[310000],w[310000];
struct SAM
{
	int cnt,tail;
	struct node{int son[26],fa,len;bool flag;}o[610000];
	void add(int x)
	{
		int p,np=++cnt,q,nq;
		o[np].len=o[tail].len+1;
		o[np].flag=1;
		for(p=tail;p&&!o[p].son[x];p=o[p].fa)
			o[p].son[x]=np;
		if(!o[p].son[x])
			o[p].son[x]=np;
		else
		{
			q=o[p].son[x];
			if(o[q].len==o[p].len+1)
				o[np].fa=q;
			else
			{
				o[nq=++cnt]=o[q];
				o[nq].flag=0;
				o[q].fa=o[np].fa=nq;
				o[nq].len=o[p].len+1;
				for(;o[p].son[x]==q;p=o[p].fa)
					o[p].son[x]=nq;
			}
		}
		tail=np;
	}
}sam;
int shu,first[610000];
struct edge
{
	int v,nx;
}o[610000];
inline void add(int u,int v)
{
	o[++shu].v=v;
	o[shu].nx=first[u];
	first[u]=shu;
}
int L,R;
long long X,ans1[310000],t1[1210000];
inline void pushdown1(int t)
{
	t1[t<<1]+=t1[t];
	t1[t<<1|1]+=t1[t];
	t1[t]=0;
}
inline void ADD(int l,int r,int t)
{
	if(L<=l&&r<=R)
	{
		t1[t]+=X;
		return;
	}
	if(t1[t])
		pushdown1(t);
	int mid=l+r>>1;
	if(mid>=L)
		ADD(l,mid,t<<1);
	if(mid<R)
		ADD(mid+1,r,t<<1|1);
}
long long ans2[310000],t2[1210000];
inline void pushdown2(int t)
{
	t2[t<<1]=MAX(t2[t<<1],t2[t]);
	t2[t<<1|1]=MAX(t2[t<<1|1],t2[t]);
	t2[t]=-1e18;
}
inline void change(int l,int r,int t)
{
	if(L<=l&&r<=R)
	{
		t2[t]=MAX(t2[t],X);
		return;
	}
	if(t2[t]>-1e18)
		pushdown2(t);
	int mid=l+r>>1;
	if(mid>=L)
		change(l,mid,t<<1);
	if(mid<R)
		change(mid+1,r,t<<1|1);
}
int s[610000],max[610000][2],min[610000][2];
inline void dfs(int x)
{
	if(sam.o[x].flag)
	{
		++s[x];		
		max[x][0]=min[x][0]=w[n-sam.o[x].len+1];
	}
	for(int i=first[x];i;i=o[i].nx)
	{
		dfs(o[i].v);
		s[x]+=s[o[i].v];
		if(max[o[i].v][1]>=max[x][0])
		{
			max[x][0]=max[o[i].v][0];
			max[x][1]=max[o[i].v][1];
		}
		else if(max[o[i].v][0]>=max[x][0]&&max[o[i].v][1]<=max[x][0])
		{
			max[x][1]=max[x][0];			
			max[x][0]=max[o[i].v][0];
		}
		else if(max[o[i].v][0]>max[x][1])
			max[x][1]=max[o[i].v][0];
		if(min[o[i].v][1]<=min[x][0])
		{
			min[x][0]=min[o[i].v][0];
			min[x][1]=min[o[i].v][1];
		}
		else if(min[o[i].v][0]<=min[x][0]&&min[o[i].v][1]>=min[x][0])
		{
			min[x][1]=min[x][0];			
			min[x][0]=min[o[i].v][0];
		}
		else if(min[o[i].v][0]<min[x][1])
			min[x][1]=min[o[i].v][0];
	}
	X=(long long)s[x]*(s[x]-1)>>1;
	L=sam.o[sam.o[x].fa].len+1,R=sam.o[x].len;
	if(L<=R)
		ADD(0,n,1);
	if(s[x]>1)
	{
		X=(long long)max[x][0]*max[x][1];
		if(X<(long long)min[x][0]*min[x][1])
			X=(long long)min[x][0]*min[x][1];
		L=0,R=sam.o[x].len;
		change(0,n,1);
	}
}
inline void find(int l,int r,int t)
{
	if(l==r)
	{
		ans1[l]=t1[t];
		return;
	}
	if(t1[t])
		pushdown1(t);
	int mid=l+r>>1;
	find(l,mid,t<<1);
	find(mid+1,r,t<<1|1);
}
inline void DFS(int l,int r,int t)
{
	if(l==r)
	{
		ans2[l]=t2[t];
		return;
	}
	if(t2[t]>-1e18)
		pushdown2(t);
	int mid=l+r>>1;
	DFS(l,mid,t<<1);
	DFS(mid+1,r,t<<1|1);
}
int main()
{
	freopen("savour.in","r",stdin);
	freopen("savour.out","w",stdout);
	memset(max,-0x3f,sizeof(max));
	memset(min,0x3f,sizeof(min));
	memset(t2,-0x3f,sizeof(t2));
	memset(ans2,-0x7f,sizeof(ans2));
	c[++n]=getchar();
	while(c[n]<'a'||c[n]>'z')
		c[n]=getchar();
	while('a'<=c[n]&&c[n]<='z')
		c[++n]=getchar();
	--n;
	for(int i=n;i;--i)
		sam.add(c[i]-97);
	long long Max1=-0x7fffffff,Max2=-0x7fffffff,Min1=0x7fffffff,Min2=0x7fffffff;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&w[i]);
		if(Max1<w[i])
		{
			Max2=Max1;
			Max1=w[i];
		}
		else if(Max2<w[i])
			Max2=w[i];
		if(Min1>w[i])
		{
			Min2=Min1;
			Min1=w[i];
		}
		else if(Min2>w[i])
			Min2=w[i];	
	}
	ans2[0]=Max1*Max2;
	if(ans2[0]<Min1*Min2)
		ans2[0]=Min1*Min2;
	for(int i=1;i<=sam.cnt;++i)
		add(sam.o[i].fa,i);
	dfs(0);
	find(0,n,1);
	DFS(0,n,1);
	ans1[0]=(long long)n*(n-1)>>1;
	for(int i=0;i<n;++i)
		if(ans2[i]<=-1e18)
			ans2[i]=0;
	for(int i=0;i<n;++i)
		printf("%lld %lld\n",ans1[i],ans2[i]);
}