看到这题我就伤心，当初想到了正解却因为各种sb原因没有写……
好吧，其实我的正解是比较挫的……
大家似乎都用了后缀数组，我用了后缀自动机（后缀树）
其实SAM是很好想得，用SAM建出后缀树后
我们考虑树上每个节点对答案的贡献，0相似就不必说了
考虑到任意两个后缀的LCP即这两个后缀所在节点的LCA的节点所能接受的最长子串mx[i]
又每个节点能接收的子串长度为[mx[fa[i]]+1,mx[i]]
我们很容易想出问题1：设节点i的子树内代表后缀的节点个数为s，那么节点i对区间[mx[fa[i]]+1,mx[i]]贡献是s*(s-1)/2
问题2：很显然找出节点i子树内max{最大*次大,最小*次小}（因为有负数），这要dfs序+线段树维护，然后区间覆盖再来个线段树……
总复杂度是O(nlogn)，实际是能过的（但是跑得似乎比SA做法慢……）
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
#define ll long long
#define N 300005
using namespace std;
const ll inf=-;
const ll small=-1000000002000000001ll;
int go[*N][],fa[*N],w[*N],mx[*N],p[*N],a[*N],b[*N],l[*N],r[*N];
struct node{ll b1,b2,s1,s2;} tree[*N];
struct way{int po,next;} e[*N];
ll ans[*N][];
int n,last,t,len;
char s[N]; void ins(int x,int y)
{
e[++len].po=y;
e[len].next=p[x];
p[x]=len;
} void add(int c,int x)
{
int np,nq,q,p=last;
np=++t; mx[np]=mx[p]+; a[np]=x; w[np]=;
for (;p&&!go[p][c];p=fa[p]) go[p][c]=np;
if (!p) fa[np]=;
else {
q=go[p][c];
if (mx[q]==mx[p]+) fa[np]=q;
else {
nq=++t; a[t]=inf;
mx[nq]=mx[p]+;
memcpy(go[nq],go[q],sizeof(go[q]));
fa[nq]=fa[q]; fa[np]=fa[q]=nq;
for (;go[p][c]==q;p=fa[p]) go[p][c]=nq;
}
}
last=go[last][c];
} void dfs(int x)
{
l[x]=++t; b[t]=x;
for (int i=p[x];i;i=e[i].next)
{
int y=e[i].po;
dfs(y); w[x]+=w[y];
}
r[x]=t;
} void update(node &a,node x,node y)
{
if (x.b1>y.b1)
{
a.b1=x.b1;
a.b2=max(x.b2,y.b1);
}
else {
a.b1=y.b1;
a.b2=max(x.b1,y.b2);
}
if (x.s1>y.s1)
{
a.s1=y.s1;
a.s2=min(x.s1,y.s2);
}
else {
a.s1=x.s1;
a.s2=min(x.s2,y.s1);
}
}
void build(int i,int l, int r)
{
if (l==r)
{
tree[i].b1=a[b[l]];
tree[i].b2=inf;
tree[i].s2=-inf;
tree[i].s1=(a[b[l]]==inf)?-inf:a[b[l]];
return;
}
int m=(l+r)>>;
build(i*,l,m);
build(i*+,m+,r);
update(tree[i],tree[i*],tree[i*+]);
} node get(int i,int l,int r,int x, int y)
{
if (x<=l&&y>=r) return tree[i];
int m=(l+r)>>;
node s,b,c;
b.b1=b.b2=c.b1=c.b2=inf;
b.s1=b.s2=c.s1=c.s2=-inf;
if (x<=m) b=get(i*,l,m,x,y);
if (y>m) c=get(i*+,m+,r,x,y);
update(s,b,c);
return s;
} void work(int i,int l,int r,int x,int y,ll a,ll b)
{
if (x<=l&&y>=r) {ans[i][]+=a; ans[i][]=max(ans[i][],b);}
else {
int m=(l+r)>>;
if (ans[i][])
{
ans[i*][]+=ans[i][]; ans[i*+][]+=ans[i][];
ans[i][]=;
}
if (ans[i][]>small)
{
ans[i*][]=max(ans[i][],ans[i*][]); ans[i*+][]=max(ans[i][],ans[i*+][]);
ans[i][]=small;
}
if (x<=m) work(i*,l,m,x,y,a,b);
if (y>m) work(i*+,m+,r,x,y,a,b);
}
} void getans(int i,int l,int r)
{
if (l==r)
{
if (ans[i][]==) ans[i][]=;
printf("%lld %lld\n",ans[i][],ans[i][]);
}
else {
int m=(l+r)>>;
if (ans[i][]>small) {ans[i*][]=max(ans[i][],ans[i*][]); ans[i*+][]=max(ans[i][],ans[i*+][]);}
if (ans[i][]) {ans[i*][]+=ans[i][]; ans[i*+][]+=ans[i][];}
getans(i*,l,m);
getans(i*+,m+,r);
}
} int main()
{
scanf("%d",&n); scanf("%s",s+);
for (int i=; i<=n; i++) scanf("%d",&b[i]);
if (n==) {puts("0 0");return ;}
t=last=; a[]=inf;
for (int i=n;i;i--) add(s[i]-'a',b[i]);
for (int i=;i<=t; i++) ins(fa[i],i);
t=; dfs();
build(,,t);
for (int i=; i<=n*;i++) ans[i][]=small;
for (int i=; i<=t; i++)
{
if (w[i]<=) continue;
node c=get(,,t,l[i],r[i]);
ll x=max(c.b1*c.b2,c.s1*c.s2);
work(,,n-,mx[fa[i]]+,mx[i],(ll)(w[i]-)*(ll)(w[i])/,x);
}
printf("%lld %lld\n",(ll)(w[]-)*(ll)(w[])/,max(tree[].b1*tree[].b2,tree[].s1*tree[].s2));
getans(,,n-);
return ;
}