sol

  1. 考虑samparent树上, 父子关系即对应着后缀关系
    lcp是最长公共前缀
    故, 建立反串的sam就可以解决问题.
  2. 发现题意就是对所有的数对(i, j)
    计算s[i…n]s[j…n]lcp

关于后缀的lcp

观察parent树, 两个后缀对应节点u, vlen(lca)就是答案.

考虑一个节点的祖先节点就是该点后缀, 而u, v到跟路径的交点就是
二者共有的后缀, 深度最深的(即lca)就是最长的\text{prefix}, 即lcp

那么可以树上dp即可.

进一步的, 求(a_i \cdot a_j) |_{\max} 由于正负不确定,
需要维护最大值与最小值, 这是后话了, 详见代码

Code

%:pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 6e5 + 10;
const int Mi = 26, inf = 1e9;

int n;
LL f[N], ans[N];
char s[N];

template <typename T>
inline void Max(T &a, T b) {
    if(b > a) a = b;
}
template <typename T>
inline void Min(T &a, T b) {
    if(b < a) a = b;
}
namespace Sam {

    int id = 1, cur = 1, p, q, nq, len[N], link[N], ch[N][26];
    int sz[N], ton[N], a[N];
    LL mx[N], mi[N];

    inline void copy(int a, int b) {
        link[a] = link[b];
        for(int i = 0; i < Mi; ++i) 
            ch[a][i] = ch[b][i];
    }
    void insert(int c, int vv) {
        p = cur;
        cur = ++id;
        len[cur] = len[p] + 1;
        sz[cur] = 1;
        mx[cur] = mi[cur] = vv;
        for(; p && !ch[p][c]; p = link[p])
            ch[p][c] = cur;
        if(!p) return (void) (link[cur] = 1);
        q = ch[p][c];
        if(len[q] == len[p] + 1) {
            link[cur] = q;
        } else {
            nq = ++id;
            copy(nq, q);
            len[nq] = len[p] + 1;
            link[q] = link[cur] = nq;
            for(int u = p; u && ch[u][c] == q; u = link[u])
                ch[u][c] = nq;
        }
    }
    void sort() {
        int mx = 0;
        for(int i = 1; i <= id; ++i)
            ++ton[len[i]], mx = max(mx, len[i]);
        for(int i = 1; i <= mx; ++i)
            ton[i] += ton[i - 1];
        for(int i = 1; i <= id; ++i)
            a[ton[len[i]]--] = i;
    }
}
using namespace Sam;

inline bool ok(int u) {
    return mx[u] != -LONG_LONG_MAX && mi[u] != LONG_LONG_MAX;
}
void solve() {
    for(int i = id, u, fa; i; --i) {
        u = a[i], fa = link[u];
        f[len[fa]] += (LL) sz[fa] * sz[u];
        if(ok(u) && ok(fa))
            Max(ans[len[fa]], max(mx[u] * mx[fa], mi[u] * mi[fa]));
        sz[fa] += sz[u];
        Max(mx[fa], mx[u]);
        Min(mi[fa], mi[u]);
    }
}
int main() {
    scanf("%d%s", &n, s + 1);
    static int val[N];
    for(int i = 1; i <= n; ++i)
        scanf("%d", val + i);
    for(int i = 0; i <= n; ++i)
        ans[i] = -2e18;
    for(int i = 0; i <= 2 * n; ++i)
        mx[i] = -LONG_LONG_MAX, mi[i] = LONG_LONG_MAX;
    for(int i = n, x; i; --i) {
        insert(s[i] - 'a', val[i]);
    }
    sort();
    solve();
    for(int i = n - 1; ~i; --i) {
        f[i] += f[i + 1];
        Max(ans[i], ans[i + 1]);
    }
    for(int i = 0; i < n; ++i)
        printf("%lld %lld\n", f[i], ans[i] == -2e18 ? 0 : ans[i]);
    return 0;
}