题意

有一个长度为 $n$ 的序列，定义后缀 $i,j$ 是 $r$ 相似的当且仅当 $[i,i+r-1]$ 的子串和 $[j,j+r-1]$ 的子串相同。后缀 $i,j$ 的权值定义为 $a_i \times a_j$。求对于所有的 $r \in [0,n-1]$，满足 $r$ 相似的 $(i,j)(i<j)$ 的个数，以及权值最大的一对的权值。

分析

先考虑第一问。

首先，如果 $i,j$ 是 $r$ 相似的，那么他们也一定是 $0 \sim r-1$ 相似的。换句话说，后缀 $i,j$ 会对 $0 \sim lcp(i,j)$ 产生贡献，这里的 $lcp(i,j)$ 表示后缀 $i,j$ 的最长公共前缀的长度。

我们可以倒过来算，那么我们就要算 $\sum_{1\le i < j \le n} [lcp(i,j) = r]$。

考虑 $lcp(i,j) = \sum_{k=rk_i+1}^{rk_j} height_k$。我们可以枚举所有 $height_k = r$ 的位置 $k$。假设左边有长度为 $l_1$ 的极长连续段是已经插入的，右边有长度为 $l_2$ 的极长连续段是已经插入的，那么就会有 $(l_1+1)(l_2+1)$ 的贡献。求 $l_1,l_2$ 可以用单调栈预处理或并查集动态维护。

考虑第二问，我们可以直接查询左右两端的最大值乘起来，以及左右两段的最小值乘起来。要最小值是因为会有负数。这里我是用 ST 表维护的，实际上应该可以并查集直接存，但是我们不想调细节。

最后时间复杂度就是 $O(n\log n)$ 的。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 600005
#define int ll
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, sa[N], oldsa[N], rk[N], oldrk[N], t[N], height[N];
int a[N], fa[N], sz[N], lg[N];
struct P{
    int op, f[N][35];
    il int get(int x, int y){return op ? max(x, y) : min(x, y);}
    il void init(){
        for (int i = 1; i <= n; i++) f[i][0] = a[i];
        for (int j = 1; j <= 30; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) f[i][j] = get(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
    il int query(int l, int r){
        int p = lg[r - l + 1];
        return get(f[l][p], f[r - (1 << p) + 1][p]);
    }
}Max, Min;
ll ans1[N], ans2[N];
char s[N];
il void ms(int *a, int v, int n){for (int i = 0; i <= n + 4; i++) a[i] = v;}
il void mc(int *a, int *b, int n){for (int i = 0; i <= n + 4; i++) a[i] = b[i];}
il int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
vector <int> pos[N];
il void SA(){
    int M = 127;
    ms(t, 0, M);
    for (int i = 1; i <= n; i++) t[rk[i] = s[i]]++;
    for (int i = 1; i <= M; i++) t[i] += t[i - 1];
    for (int i = n; i >= 1; i--) sa[t[rk[i]]--] = i;
    for (int w = 1; w < n; w <<= 1, M = n){
        mc(oldsa, sa, n), ms(t, 0, M);
        for (int i = 1; i <= n; i++) t[rk[oldsa[i] + w]]++;
        for (int i = 1; i <= M; i++) t[i] += t[i - 1];
        for (int i = n; i >= 1; i--) sa[t[rk[oldsa[i] + w]]--] = oldsa[i];
        mc(oldsa, sa, n), ms(t, 0, M);
        for (int i = 1; i <= n; i++) t[rk[oldsa[i]]]++;
        for (int i = 1; i <= M; i++) t[i] += t[i - 1];
        for (int i = n; i >= 1; i--) sa[t[rk[oldsa[i]]]--] = oldsa[i];
        mc(oldrk, rk, n);
        for (int p = 0, i = 1; i <= n; i++)
            if (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) rk[sa[i]] = p;
            else rk[sa[i]] = ++p;
    }
}
il void HT(){
    for (int i = 1, k = 0; i <= n; i++) if (rk[i] >= 1){
        if (k) k--;
        while (i + k <= n && sa[rk[i] - 1] + k <= n && s[i + k] == s[sa[rk[i] - 1] + k]) k++;
        height[rk[i]] = k;
    }
}
signed main(){
    n = rd(), scanf ("%s", s + 1), SA(), HT(), Max.op = 1, height[1] = -1;
    for (int i = 1; i <= n; i++) a[rk[i]] = rd(), fa[i] = i, sz[i] = 1;
    for (int i = 2; i <= n; i++) pos[height[i]].push_back(i), lg[i] = lg[i >> 1] + 1;

    Max.init(), Min.init();
    ll a1 = 0, a2 = -1e18;
    for (int i = n - 1; i >= 0; i--){
        for (int p : pos[i]){
            if (height[p - 1] >= height[p] && height[p + 1] > height[p]){
                int pa = find(p - 1), pb = find(p + 1);
                a1 += 1ll * (sz[pa] + 1) * (sz[pb] + 1);
                a2 = max(a2, 1ll * Max.query(p - sz[pa] - 1, p - 1) * Max.query(p, p + sz[pb]));
                a2 = max(a2, 1ll * Min.query(p - sz[pa] - 1, p - 1) * Min.query(p, p + sz[pb])); 
                sz[find(p)] += sz[pa] + sz[pb], fa[pa] = find(p), fa[pb] = find(p);
            }
            else if (height[p - 1] >= height[p]){
                int pa = find(p - 1);
                a1 += sz[pa] + 1;
                a2 = max(a2, 1ll * Max.query(p - sz[pa] - 1, p - 1) * a[p]);
                a2 = max(a2, 1ll * Min.query(p - sz[pa] - 1, p - 1) * a[p]);
                sz[find(p)] += sz[pa], fa[pa] = find(p);
            }
            else if (height[p + 1] > height[p]){
                int pb = find(p + 1);
                a1 += sz[pb] + 1;
                a2 = max(a2, 1ll * a[p - 1] * Max.query(p, p + sz[pb]));
                a2 = max(a2, 1ll * a[p - 1] * Min.query(p, p + sz[pb]));
                sz[find(p)] += sz[pb], fa[pb] = find(p);
            }
            else a1++, a2 = max(a2, 1ll * a[p - 1] * a[p]);
        }
        if (a1) ans1[i] = a1, ans2[i] = a2;
    }
    for (int i = 0; i < n; i++) printf ("%lld %lld\n", ans1[i], ans2[i]);
    return 0;
}