noi2015品酒大会（sa）

用常用的套路，排序之后从大到小插入height，用并查集维护即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
const ll inf=1e18;
int n,sa[maxn],H[maxn],ra[maxn],tong[maxn],m,tp[maxn],fa[maxn];
ll ans1[maxn],ans2[maxn],c[maxn];
char s[maxn];
int getfa(int x){return (x==fa[x])?x:fa[x]=getfa(fa[x]);}
void rsort(){
    for(int i=;i<=m;++i)tong[i]=;
    for(int i=;i<=n;++i)tong[ra[tp[i]]]++;
    for(int i=;i<=m;++i)tong[i]+=tong[i-];
    for(int i=n;i>=;--i)sa[tong[ra[tp[i]]]--]=tp[i];
}
int cmp(int x,int y,int w){return tp[x]==tp[y]&&tp[x+w]==tp[y+w];}
void pre(){
    for(int i=;i<=n;++i)ra[i]=s[i]-'a'+,tp[i]=i;    m=;rsort();    for(int w=,p=,i;p<n;w+=w,m=p){
        for(p=,i=n-w+;i<=n;++i)tp[++p]=i;
        for(i=;i<=n;++i)if(sa[i]>w)tp[++p]=sa[i]-w;
        rsort();swap(tp,ra);ra[sa[]]=p=;
        for(i=;i<=n;++i)ra[sa[i]]=cmp(sa[i],sa[i-],w)?p:++p;
    }
    int j,k=;
    for(int i=;i<=n;H[ra[i++]]=k)
        for(k=k?k-:k,j=sa[ra[i]-];s[i+k]==s[j+k];++k);
}
struct node{
    int id,v;
    bool operator<(const node&t)const{
        return v<t.v;
    }
}tmp[maxn];
struct lian{
    int l,r;
    ll ma,mi,len;
}a[maxn];
void merge(int x,int y,int w){
    x=getfa(x);y=getfa(y);
    ll t1=max(a[x].ma*a[y].ma,a[x].mi*a[y].mi);
    ll t2=max(a[x].ma*a[y].mi,a[x].mi*a[y].ma);
    ll t3=min(a[x].ma*a[y].ma,a[x].mi*a[y].mi);
    ll t4=min(a[x].ma*a[y].mi,a[x].mi*a[y].ma);
    a[x].ma=max(a[x].ma,a[y].ma);
    a[x].mi=min(a[y].mi,a[x].mi);
    ans1[w]+=a[x].len*a[y].len;
    a[x].len+=a[y].len;
    fa[y]=x;
    ans2[w]=max(ans2[w],max(t1,t2));}
int main(){
    cin>>n;
    scanf("%s",s+);
    pre();
    for(int i=;i<=n;++i){
        tmp[i-].id=i,tmp[i-].v=H[i];
    }
    sort(tmp+,tmp+n);
    for(int i=;i<=n;++i)scanf("%lld",&c[i]);
    for(int i=;i<=n;++i){
        a[i].mi=a[i].ma=c[sa[i]];
        a[i].l=a[i].r=i;a[i].len=;
        fa[i]=i;
    }
    //for(int i=1;i<=n;++i)cout<<sa[i]<<' '<<H[i]<<endl;
    for(int i=;i<=n;++i)ans2[i]=-inf;
    for(int i=n-;i>=;--i){
        merge(tmp[i].id-,tmp[i].id,tmp[i].v);
    }
    for(int i=n-;i>=;--i){
        ans1[i]+=ans1[i+];
        ans2[i]=max(ans2[i],ans2[i+]);
    }
    for(int i=;i<=n-;++i){
        printf("%lld ",ans1[i]);
        if(ans2[i]==-inf)printf("%lld\n",);
        else printf("%lld\n",ans2[i]);
    }
    return ;
}