记录编号	483676	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]品酒大会	最终得分	100
用户昵称	Hzoi_moyi	是否通过	通过
代码语言	C++	运行时间	2.815 s
提交时间	2018-01-18 17:49:42	内存使用	127.63 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int sj=300010;
int n,m,a[sj],tx[sj],ty[sj],rk[sj],sa[sj],h[sj],a1,a2,fa[sj];
ll vl[sj],ans1[sj],ans2[sj],sum,ans,tp1,tp2,tp,tp3,tp4,qwq,mx[sj],mi[sj],num[sj];
char s[sj];
struct ls
{
    int num,val;
}ss[sj];
struct tree
{
    int lc,rc,sum;
}t[sj*30];
int comp(const ls&x,const ls&y)
{
	return x.val<y.val;
}
void rsort()
{
	memset(tx,0,sizeof(int)*(m+1));
    for(int i=1;i<=n;i++)  tx[rk[ty[i]]]++;
    for(int i=1;i<=m;i++)  tx[i]+=tx[i-1];
    for(int i=n;i>=1;i--)  sa[tx[rk[ty[i]]]--]=ty[i];
}
void suffix()
{
	int i,j,k,l,p;
	for(i=1;i<=n;i++)  rk[i]=a[i],ty[i]=i;
	m=26;rsort();
	for(p=1,l=1;p<n;m=p,l<<=1)
	{
	    for(p=0,i=n-l+1;i<=n;i++)  ty[++p]=i;
	    for(i=1;i<=n;i++)  if(sa[i]>l)  ty[++p]=sa[i]-l;
	    rsort(),swap(ty,rk),rk[sa[1]]=p=1;
	    for(i=2;i<=n;i++) 
	        rk[sa[i]]=(ty[sa[i]]==ty[sa[i-1]]&&ty[sa[i]+l]==ty[sa[i-1]+l])?p:++p;
	}
	for(i=1,k=0;i<=n;h[rk[i++]]=k)
	    for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);
} 
void init()
{
	scanf("%d%s",&n,s);
	memset(fa,-1,sizeof(fa));
	tp1=-1ll<<62,tp2=-1ll<<62,tp3=1ll<<62,tp4=1ll<<62;
    for(int i=1;i<=n;i++)  
	{    
		scanf("%lld",&vl[i]);
        a[i]=s[i-1]-'a'+1;
        if(vl[i]>=tp1)  tp2=tp1,tp1=vl[i];  
        else if(vl[i]>tp2)  tp2=vl[i];
        if(vl[i]<=tp3)  tp4=tp3,tp3=vl[i];
		else if(vl[i]<tp4)  tp4=vl[i];  
	}
}
int find(int x)
{
    if(fa[x]==-1)  return x;
    return fa[x]=find(fa[x]);
}
inline ll maxx(ll x,ll y)
{
	return x>y?x:y;
}
inline ll minn(ll x,ll y)
{
    return x<y?x:y;
}
int main()
{
	freopen("savour.in","r",stdin);
	freopen("savour.out","w",stdout);
    init();
	suffix();
	for(int i=1;i<=n;i++)
	{
	    ss[i].num=i,ss[i].val=h[i];
        num[i]=1,mx[i]=mi[i]=vl[sa[i]];
	}
	sort(ss+1,ss+n+1,comp);
	ans=-1ll<<62;
	for(int i=n;i>=1;i--)
	{
		if(ss[i].val!=ss[i+1].val)  
		    ans1[ss[i+1].val]=sum/2,ans2[ss[i+1].val]=ans;
		a1=ss[i].num,a2=a1-1;
		if(!h[a1])  break;
		a1=find(a1),a2=find(a2);
		sum-=(ll)num[a1]*(num[a1]-1);
	    sum-=(ll)num[a2]*(num[a2]-1);
	    tp=mx[a1]*mx[a2],qwq=mi[a1]*mi[a2];
	    if(tp>ans)   ans=tp;
	    if(qwq>ans)  ans=qwq;
	    if(num[a1]<num[a2])  swap(a1,a2);
	    mx[a1]=maxx(mx[a1],mx[a2]);
	    mi[a1]=minn(mi[a1],mi[a2]);
	    num[a1]+=num[a2];
	    fa[a2]=a1;
	    sum+=(ll)num[a1]*(num[a1]-1);
	}
	ans1[0]=(ll)n*(n-1)/2,ans2[0]=maxx(tp1*tp2,tp3*tp4);
	for(int i=0;i<n;i++)
	    printf("%lld %lld\n",ans1[i],ans2[i]);
	return 0;
}