来自FallDream的博客，未经允许，请勿转载，谢谢
n<=3*10^5
有一道题很类似 我写了两种做法 戳这里
这道理也可以类似做，建出笛卡尔树之后维护子树最大最小值(负负得正)就行了
没判负负得正爆了一次。
#include<iostream> #include<cstdio> #include<cstring> #define MN 300000 #define N 524288 #define ll long long #define INF 2000000000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } char st[MN*2+5]; int v[MN+5],n,H[MN+5],s[MN+5],S[MN+5],size[MN+5],p=1,q=0,k=1; int sa[2][MN+5],rk[2][MN+5],Q[MN+5],top=0,L[MN+5],R[MN+5],mx[MN+5],mx2[MN+5],lt[MN+5],mn[MN+5],mn2[MN+5]; ll Ans[MN+5],Mx[MN+5]; void CalcSA(int*SA,int*RK,int*sa,int*rk) { for(int i=1;i<=n;++i) v[rk[sa[i]]]=i; for(int i=n;i;--i) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k; for(int i=n-k+1;i<=n;++i) SA[v[rk[i]]--]=i; for(int i=1;i<=n;++i) RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]); } void GetH(int*sa,int*rk) { for(int i=1,k=0;i<=n;H[rk[i++]]=k,k==0?0:--k) if(rk[i]!=1) for(int j=sa[rk[i]-1];st[j+k]==st[i+k];++k); } int Build() { for(int i=2;i<=n;++i) { int last=0; while(top&&H[Q[top]]>=H[i]) last=Q[top--]; if(top) R[Q[top]]=i; L[Q[++top]=i]=last; } return Q[1]; } inline void Up(int&a,int&b,int c) { if(c>a) b=a,a=c; else if(c>b) b=c; } inline void UP(int&a,int&b,int c) { if(c<a) b=a,a=c; else if(c<b) b=c; } void Dfs(int x) { lt[x]=S[x-1]; if(L[x]) Dfs(L[x]),lt[x]=lt[L[x]]; if(R[x]) Dfs(R[x]); size[x]=size[L[x]]+size[R[x]]+1; Up(mx[x],mx2[x],S[x]); UP(mn[x],mn2[x],S[x]); if(L[x])Up(mx[x],mx2[x],mx[L[x]]), Up(mx[x],mx2[x],mx2[L[x]]), UP(mn[x],mn2[x],mn[L[x]]), UP(mn[x],mn2[x],mn2[L[x]]); if(R[x])Up(mx[x],mx2[x],mx[R[x]]), Up(mx[x],mx2[x],mx2[R[x]]), UP(mn[x],mn2[x],mn[R[x]]), UP(mn[x],mn2[x],mn2[R[x]]); Ans[H[x]]+=1LL*(size[L[x]]+1)*(size[R[x]]+1); Mx[H[x]]=max(Mx[H[x]],1LL*mx[x]*max(lt[x],mx2[x])); if(mn[x]<=0&&min(mn2[x],lt[x])<=0) Mx[H[x]]=max(Mx[H[x]],1LL*mn[x]*min(mn2[x],lt[x])); } int main() { memset(Mx,128,sizeof(Mx)); memset(mx,128,sizeof(mx)); memset(mx2,128,sizeof(mx2)); memset(mn,127,sizeof(mn)); memset(mn2,127,sizeof(mn2)); n=read();scanf("%s",st+1); for(int i=1;i<=n;++i) s[i]=read(); for(int i=1;i<=n;++i) ++v[st[i]-'a']; for(int i=1;i<26;++i) v[i]+=v[i-1]; for(int i=1;i<=n;++i) sa[q][v[st[i]-'a']--]=i; for(int i=1;i<=n;++i) rk[q][sa[q][i]]=rk[q][sa[q][i-1]]+(st[sa[q][i]]!=st[sa[q][i-1]]); for(k=1;k<n;k<<=1) { CalcSA(sa[p],rk[p],sa[q],rk[q]); swap(p,q); } GetH(sa[q],rk[q]); for(int i=1;i<=n;++i) S[rk[q][i]]=s[i]; int rt=Build();Dfs(rt); for(int i=n-1;~i;--i) Mx[i]=max(Mx[i],Mx[i+1]),Ans[i]+=Ans[i+1]; for(int i=0;i<n;++i) printf("%lld %lld ",Ans[i],!Ans[i]?0:Mx[i]); return 0; }