做法同差异。
后缀数组+单调栈+线段树。
单调栈维护每个数前后第一个比它小的数的位置，就可以确定一个hight是一段区间的最小值，然后线段树查询一下区间最值更新答案即可。
调了好久。。。线段树只开了2倍空间把自己炸死了。
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#define inf 1e18
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=300007;
typedef long long LL;
using namespace std;
char s[N];
int n,sa[N],rak[N],h[N];
LL ans[N],cnt[N],v[N];
template<typename T> void read(T &x) {
T f=1; x=0; char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}
void make_hight() {
For(i,0,n-1) rak[sa[i]]=i;
int k=0;
For(i,0,n-1) {
if(!rak[i]) continue;
if(k) k--;
int j=sa[rak[i]-1];
while(s[i+k]==s[j+k]) k++;
h[rak[i]]=k;
}
}
int cmp(int a,int b,int k,int y[]) {
int o1=a+k>=n?-1:y[a+k];
int o2=b+k>=n?-1:y[b+k];
return o1==o2&&y[a]==y[b];
}
void make_sa() {
static int t1[N],t2[N],c[N];
int *x=t1,*y=t2,p=0,m='z'+1;
For(i,0,m-1) c[i]=0;
For(i,0,n-1) c[x[i]=s[i]]++;
For(i,1,m-1) c[i]+=c[i-1];
Rep(i,n-1,0) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1) {
p=0;
For(i,n-k,n-1) y[p++]=i;
For(i,0,n-1) if(sa[i]>=k) y[p++]=sa[i]-k;
For(i,0,m-1) c[i]=0;
For(i,0,n-1) c[x[y[i]]]++;
For(i,1,m) c[i]+=c[i-1];
Rep(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
swap(x,y); x[sa[0]]=0; p=1;
For(i,1,n-1)
x[sa[i]]=cmp(sa[i],sa[i-1],k,y)?p-1:p++;
if(p==n) break;
m=p;
}
make_hight();
}
LL sgmx[N<<2],sgmi[N<<2];
#define lc x<<1
#define rc (x<<1|1)
#define mid ((l+r)>>1)
void build(int x,int l,int r) {
if(l==r) { sgmx[x]=sgmi[x]=v[sa[l-1]+1]; return; }
build(lc,l,mid); build(rc,mid+1,r);
sgmx[x]=max(sgmx[lc],sgmx[rc]);
sgmi[x]=min(sgmi[lc],sgmi[rc]);
}
LL qry(int x,int l,int r,int ql,int qr,int f) {
if(ql>qr) return -inf;
if(l>=ql&&r<=qr) return f?sgmx[x]:sgmi[x];
if(qr<=mid) return qry(lc,l,mid,ql,qr,f);
if(ql>mid) return qry(rc,mid+1,r,ql,qr,f);
return f?(max(qry(lc,l,mid,ql,qr,f),qry(rc,mid+1,r,ql,qr,f))):(
min(qry(lc,l,mid,ql,qr,f),qry(rc,mid+1,r,ql,qr,f))
);
}
int sta[N],top,ll[N],rr[N];
void solve() {
For(i,1,n-1) {
while(top&&h[sta[top]]>=h[i]) top--;
if(top) ll[i]=sta[top];
else ll[i]=0;
sta[++top]=i;
} top=0;
Rep(i,n-1,1) {
while(top&&h[sta[top]]>h[i]) top--;
if(top) rr[i]=sta[top]-1;
else rr[i]=n-1;
sta[++top]=i;
}
For(i,1,n-1) {
LL t1=qry(1,1,n,ll[i]+1,i-2+1,1);
LL t2=qry(1,1,n,i+1,rr[i]+1,1);
LL t3=qry(1,1,n,ll[i]+1,i-2+1,0);
LL t4=qry(1,1,n,i+1,rr[i]+1,0);
LL tpans=-inf;
if(t1!=-inf&&t2!=-inf) tpans=max(tpans,t1*t2);
if(t1!=-inf) tpans=max(tpans,t1*v[sa[i-1]+1]);
if(t2!=-inf) tpans=max(tpans,t2*v[sa[i-1]+1]);
if(t4!=-inf&&t3!=-inf) tpans=max(tpans,t3*t4);
if(t3!=-inf) tpans=max(tpans,v[sa[i-1]+1]*t3);
if(t4!=-inf) tpans=max(tpans,v[sa[i-1]+1]*t4);
cnt[h[i]]+=(LL)(i-ll[i])*(rr[i]-i+1);
ans[h[i]]=max(ans[h[i]],tpans);
}
Rep(i,n-2,0) { ans[i]=max(ans[i],ans[i+1]); cnt[i]+=cnt[i+1]; }
}
//#define DEBUG
int main() {
#ifdef DEBUG
freopen("1.out","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n);
scanf("%s",s);
For(i,1,n) read(v[i]);
make_sa();
build(1,1,n);
For(i,0,n-1) ans[i]=-inf;
solve();
For(i,0,n-1) if(ans[i]==-inf) ans[i]=0;
For(i,0,n-1) printf("%lld %lld
",cnt[i],ans[i]);
return 0;
}