后缀数组笔记。

首先 $ans_i$ 的答案可以从 $ans_{i+1}$ 累加过来，因此我们考虑相似度恰好为 $i$ 对答案的贡献。
相当于两个后缀 $a,b$ 的 LCP 长度恰好为 $i$，即 $[rk_a,rk_b]$ 的 $\min \{ height \}$ 必须恰好等于 $i$。
这玩意儿很难做，但是我们可以考虑从大到小加入 Height。
这样转化的巧妙之处在于 $\lt i$ 的 height 都没有被加入，因此不会影响统计。
那么加入一个 height 相当于是合并两个连通块，同时还要维护连通块的 $\max,\min,siz$。

#include <bits/stdc++.h>
#define PLL pair<long long, long long>
using namespace std;
const int N = 6e5 + 5;
const long long INF = 1e18;
int n, a[N];
char s[N];

int sa[N], rk[N], cnt[N], x[N << 1], y[N << 1];
void init_SA() {
    int v = 128;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) cnt[x[i] = s[i]]++;
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;

    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > len) y[++tot] = sa[i] - len;

        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) cnt[x[i]]++;
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;

        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++)
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        v = tot;
        if (v == n) break;
    }
}

int ht[N];
void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
        j = sa[rk[i] - 1], now = max(0, now - 1);
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++;
        ht[rk[i]] = now;
    }
}

int p[N], id[N], mx[N], mn[N], sz[N];
bool cmp(int a, int b) { return ht[a] > ht[b]; }
int find(int x) { return (p[x] == x) ? x : p[x] = find(p[x]); }
long long get(int x) { return x * 1ll * (x - 1) / 2; }
PLL merge(int x, int y) {
    x = find(x), y = find(y);
    long long res1 = get(sz[x] + sz[y]) - get(sz[x]) - get(sz[y]), res2 = max(mn[x] * 1ll * mn[y], mx[x] * 1ll * mx[y]);
    p[x] = y, mx[y] = max(mx[x], mx[y]), mn[y] = min(mn[x], mn[y]), sz[y] += sz[x];
    return make_pair(res1, res2);
}
long long ans1[N], ans2[N];

void clr() {
    for (int i = 0; i <= n; i++) sa[i] = rk[i] = ht[i] = 0, ans1[i] = 0ll, ans2[i] = -INF;
    for (int i = 0; i <= n * 2; i++) x[i] = y[i] = 0;
}

void solve() {
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1, mx[i] = mn[i] = a[sa[i]];
    for (int i = 1; i <= n; i++) id[i] = i;
    sort(id + 1, id + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        int x = id[i];
        PLL res;
        if (x > 1 && (find(x) ^ find(x - 1)) ) res = merge(x - 1, x), ans1[ht[x]] += res.first, ans2[ht[x]] = max(ans2[ht[x]], res.second);
    }
    for (int i = n - 1; i >= 0; i--) ans1[i] += ans1[i + 1], ans2[i] = max(ans2[i], ans2[i + 1]);
    for (int i = 0; i < n; i++) printf("%lld %lld\n", ans1[i], (ans1[i] == 0) ? 0ll : ans2[i]);
}

int main() {
    scanf("%d\n %s\n ", &n, s + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    clr();
    init_SA(), init_height();
    solve();
    return 0;
}