需要注意的事情太多了，必须回顾的提
/************************************************************** Problem: 4199 User: zhhx Language: C++ Result: Wrong_Answer ****************************************************************/ #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #define maxn 400005 using namespace std; typedef long long ll; int s[maxn],sa[maxn],h[maxn],c[maxn],rk[maxn],t1[maxn],t2[maxn],n;ll t[maxn]; char ss[maxn]; void build_sa() { int m=30,*x=t1,*y=t2; for (int i=0;i<m;i++) c[i]=0; for (int i=0;i<n;i++) c[x[i]=s[i]]++; for (int i=1;i<m;i++) c[i]+=c[i-1]; for (int i=n-1;i>=0;i--) sa[--c[x[i]]]=i; for (int k=1;k<=n;k<<=1) { int p=0; for (int i=n-k;i<n;i++) y[p++]=i; for (int i=0;i<n;i++) if (sa[i]>=k) y[p++]=sa[i]-k; for (int i=0;i<m;i++) c[i]=0; for (int i=0;i<n;i++) c[x[y[i]]]++; for (int i=1;i<m;i++) c[i]+=c[i-1]; for (int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for (int i=1;i<n;i++) x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++; if (p>=n) break; m=p; } } void build_height() { int k=0; for (int i=0;i<n;i++) rk[sa[i]]=i; for (int i=0;i<n-1;i++) { if (k) k--; while (s[i+k]==s[sa[rk[i]-1]+k]) k++; h[rk[i]]=k; } } int fa[maxn],size[maxn]; ll ans2[maxn],ans1[maxn],mx[maxn],mi[maxn]; struct aa { int h,i; bool operator <(const aa &b)const { return h>b.h; } }a[maxn]; int find(int i) {return i==fa[i]?i:fa[i]=find(fa[i]);} void merge(int l,int r) { fa[l]=r; size[r]+=size[l]; mx[r]=max(mx[r],mx[l]); mi[r]=min(mi[r],mi[l]); } void work() { for (int i=1;i<n;i++) a[i].i=i,a[i].h=h[i],mx[i]=mi[i]=t[sa[i]]; for (int i=0;i<=n;i++) ans2[i]=-1e18; sort(a+1,a+n); for (int j=a[1].h,i=1;j>=0;j--) { ans1[j]=ans1[j+1];ans2[j]=ans2[j+1]; for (;i<n&&a[i].h==j;i++) { int r=find(a[i].i),l=find(a[i].i-1); if (a[i].i==1) continue; ans1[j]+=1ll*size[r]*size[l]; ans2[j]=max(ans2[j],mx[r]*mx[l]); ans2[j]=max(ans2[j],mi[r]*mi[l]); // printf("%d %lld %lld\n",j,mx[l],mi[r]); merge(l,r); } } } int main() { scanf("%d",&n); scanf("%s",ss); for (int i=0;i<n;i++) s[i]=ss[i]-'a'+1; for (int i=0;i<n;i++) scanf("%lld",&t[i]); s[n++]=0; build_sa(); build_height(); for (int i=1;i<n;i++) fa[i]=i,size[i]=1; work(); for (int i=0;i<n-1;i++) if (ans1[i]) printf("%lld %lld\n",ans1[i],ans2[i]); else printf("0 0\n"); return 0; }总结1：注意后缀数组当中的n，因为build_sa，所以会比一般的n大，这个地方错了好长时间，他会比本来的大1
2：注意a[i].i==1，再减一会不合法，所以要特盘
3:1ll，技巧
4：后缀树组必须好好注意下标的问题
