rt,在数组开到3e5+10的的情况下AC,但是开到1e6+10建SA的时候都会RE(其中挂的一个点#3应该是全a的字符串?),但把建SA的代码放到luogu和loj的后缀排序模板又都能过...

数组大小3e5+10

数组大小3.7e5+10

数组大小4e5+10

数组大小1e6+10

loj后缀排序

代码:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
char s[300010];
int sa[300010],rk[300010],h[300010],n;
void buildsuffixarrayandh(){
    static int src[300010],key[300010],cnt[300010],V;
    auto cntsort=[](int*to){
        fill_n(cnt,V+1,0);
        for(int i=1;i<=n;i++)cnt[key[i]]++;
        for(int i=1;i<=V;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i;i--)to[cnt[key[i]]--]=src[i];
    };key[0]=-1;
    V=26;for(int i=1;i<=n;i++)rk[src[i]=i]=key[i]=s[i]-'a';
    cntsort(sa);
    for(int m=1,p=0;p<n;V=p,m<<=1){
        p=0;for(int i=n;i>n-m;i--)src[++p]=i;
        for(int i=1;i<=n;i++)if(sa[i]>m)src[++p]=sa[i]-m;
        for(int i=1;i<=n;i++)key[i]=rk[src[i]];
        cntsort(sa);
        copy_n(rk+1,n,key+1);
        p=0;for(int i=1;i<=n;i++)
        rk[sa[i]]=key[sa[i]]==key[sa[i-1]]&&key[sa[i]+m]==key[sa[i-1]+m]?p:++p;
    }
    for(int i=1;i<=n;i++)
    for(h[i]=max(h[i-1]-1,0);s[i+h[i]]==s[sa[rk[i]-1]+h[i]];h[i]++);
}
int fa[300010],sz[300010],mx[300010],mi[300010];
ll cnt,mxval=-1e18;
int fr(int x){return fa[x]?fa[x]=fr(fa[x]):x;};
void uniondsu(int x,int y){
    x=fr(x),y=fr(y);
    cnt+=sz[x]*1ll*sz[y],
    mxval=max({mxval,mx[x]*1ll*mx[y],mi[x]*1ll*mi[y]});
    mx[x]=max(mx[x],mx[y]),mi[x]=min(mi[x],mi[y]);
    sz[x]+=sz[y];
    fa[y]=x;
}
int main(){
    scanf("%d%s",&n,s+1);
    buildsuffixarrayandh();
    vector<vector<int>>qwq(n);
    for(int i=1;i<=n;i++)qwq[h[i]].push_back(i);
    vector<pair<ll,ll>>ans(n);
    for(int i=1;i<=n;i++)sz[i]=1,scanf("%d",&mx[i]),mi[i]=mx[i];
    for(int r=n-1,c=0;r>=0;r--){
        for(int x:qwq[r])if(rk[x]>1)uniondsu(sa[rk[x]-1],x),c=1;
        ans[r]={cnt,c?mxval:0};
    }for(auto x:ans)printf("%lld %lld\n",x.first,x.second);
    return 0;
}