水是水，但是写出了不少问题，因此写一发博客。
https://www.luogu.org/problemnew/show/P2178
https://www.lydsy.com/JudgeOnline/problem.php?id=4199
http://uoj.ac/problem/131
首先我们知道，反串SAM就是原串的后缀树，所以两个后缀的LCP就是反串SAM parent树上的LCA。
可是这个LCP的长度绝对不是LCA的深度，而应该是LCA的len. 所以我们对于每个节点统计它作为LCA的祖先，也就是从它的子树里选出两个的方案数，然后给([len_{fa_i}+1,len_i])区间加上这个数。
另外一点是我们只需要记录最大次大和最小次小，其余的都是多余的，比如最小正数和最大负数啥的，都没有必要记录。
合并最大和次大的过程要特别注意，容易错。
最后就是后缀自动机上所有点的(r-l+1)之和是(O(n^2))级别的，会T，因此需要差分。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define llong long long
using namespace std;
const int N = 3e5;
const int S = 26;
const llong INF = (1ll<<61);
int n;
struct SuffixAutomaton
{
int oid[(N<<1)+3],buc[(N<<1)+3];
int fa[(N<<1)+3],son[(N<<1)+3][S+3],len[(N<<1)+3],sz[(N<<1)+3];
int dep[(N<<1)+3];
llong mx1[(N<<1)+3],mn1[(N<<1)+3],mx2[(N<<1)+3],mn2[(N<<1)+3];
llong ans1[N+3],ans2[N+3];
llong a[(N<<1)+3];
int siz,lstpos,rtn;
void init() {siz = lstpos = rtn = 1;}
void insertchar(char ch,llong x)
{
int p = lstpos,np; siz++; np = lstpos = siz; sz[np] = 1; len[np] = len[p]+1; a[np] = x;
for(; p && son[p][ch]==0; p=fa[p]) son[p][ch] = np;
if(p==0) {fa[np] = 1;}
else
{
int q = son[p][ch];
if(len[q]==len[p]+1) {fa[np] = q;}
else
{
siz++; int nq = siz; len[nq] = len[p]+1; a[nq] = -(1<<30);
memcpy(son[nq],son[q],sizeof(son[q]));
fa[nq] = fa[q]; fa[q] = fa[np] = nq;
for(; p && son[p][ch]==q; p=fa[p]) son[p][ch] = nq;
}
}
}
void SAMsort()
{
for(int i=1; i<=siz; i++) buc[i] = 0;
for(int i=1; i<=siz; i++) buc[len[i]]++;
for(int i=1; i<=siz; i++) buc[i] += buc[i-1];
for(int i=siz; i>=1; i--) oid[buc[len[i]]--] = i;
dep[rtn] = 0;
for(int i=1; i<=siz; i++) mx1[i] = mx2[i] = -INF,mn1[i] = mn2[i] = INF;
for(int i=0; i<=n; i++) ans2[i] = -INF;
for(int i=2; i<=siz; i++)
{
int u = oid[i];
dep[u] = dep[fa[u]]+1;
if(sz[u]==0) continue;
mx1[u] = mn1[u] = a[u];
}
for(int i=siz; i>=2; i--)
{
int u = oid[i];
sz[fa[u]] += sz[u];
if(mx1[u]>=mx1[fa[u]])
{
mx2[fa[u]] = max(mx1[fa[u]],mx2[u]);
mx1[fa[u]] = mx1[u];
}
else
{
if(mx1[u]>mx2[fa[u]]) {mx2[fa[u]] = mx1[u];}
}
if(mn1[u]<=mn1[fa[u]])
{
mn2[fa[u]] = min(mn1[fa[u]],mn2[u]);
mn1[fa[u]] = mn1[u];
}
else
{
if(mn1[u]<mn2[fa[u]]) {mn2[fa[u]] = mn1[u];}
}
}
len[0] = -1;
for(int i=1; i<=siz; i++)
{
int u = oid[i];
llong num = (llong)sz[u]*((llong)sz[u]-1ll)/2ll;
llong mxp = max(mx2[u]==-INF ? -INF : mx1[u]*mx2[u],mn2[u]==INF ? -INF : mn1[u]*mn2[u]);
ans1[len[fa[u]]+1] += num; ans1[len[u]+1] -= num; ans2[len[u]] = max(ans2[len[u]],mxp);
}
for(int i=1; i<=n; i++) ans1[i] += ans1[i-1];
for(int i=n-1; i>=0; i--) ans2[i] = max(ans2[i],ans2[i+1]);
for(int i=0; i<n; i++) {printf("%lld %lld
",ans1[i],ans1[i]==0ll ? 0ll : ans2[i]);}
}
} sam;
char str[N+3];
llong a[N+3];
int main()
{
sam.init();
scanf("%d",&n);
scanf("%s",str+1);
for(int i=1; i<n+1-i; i++) swap(str[i],str[n+1-i]);
for(int i=n; i>=1; i--) scanf("%lld",&a[i]);
for(int i=1; i<=n; i++) sam.insertchar(str[i]-96,a[i]);
sam.SAMsort();
return 0;
}