首页 题解

# Description

Luogu传送门

# Solution

首先有一个明显的结论，如果两个子串是 ii 相似，那么它们也一定是 1≤j≤i1 \leq j \leq i 相似。

所以我们可以通过 SA 把 height 数组求出来，然后从大到小排序，并依次枚举。

每次对两个相邻的后缀进行处理，把它们两个所在的并查集合并。

考虑合并都有哪些操作，回顾一下问题，我们需要计算 kk 相似的个数及最大权值。

  • 先看个数：由于我们是按 height 数组从大到小枚举的，所以已经在并查集里的子串一定是合法的，所以 ans1+=sizx×sizyans_1 += siz_x \times siz_y

  • 最大权值：这里我们需要开个数组记录一下每个并查集内的最大值和最小值（可能出现负负得正的情况），然后 ans2=max(maxsx×maxsy,minsx×minsy)ans_2 = max(maxs_x \times maxs_y, mins_x \times mins_y)

至此这道题就做完啦！

# Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N = 3e5 + 10;
ll n, m = 130;
char s[N];
ll a[N], rk[N], cnt[N], sa[N], tmp[N], hei[N];

inline void update(ll Rk[], ll tp[]){
    for(ll i = 1; i <= m; ++i) cnt[i] = 0;
    for(ll i = 1; i <= n; ++i) cnt[Rk[tp[i]]]++;
    for(ll i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for(ll i = n; i; --i) sa[cnt[Rk[tp[i]]]--] = tp[i];    
}

inline void build_sa(){
    ll *Rk = rk, *tp = tmp;
    for(ll i = 1; i <= n; ++i) Rk[i] = s[i], tp[i] = i;
    update(Rk, tp);
    ll p = 1;
    for(ll len = 1; p < n; m = p, len <<= 1){
        p = 0;
        for(ll i = n - len + 1; i <= n; ++i) tp[++p] = i;
        for(ll i = 1; i <= n; ++i)
            if(sa[i] > len) tp[++p] = sa[i] - len;
        update(Rk, tp);
        swap(Rk, tp);
        Rk[sa[1]] = p = 1;
        for(ll i = 2; i <= n; ++i)
            Rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]]) && (tp[sa[i] + len] == tp[sa[i - 1] + len]) ? p : ++p;
    }
    for(ll i = 1; i <= n; ++i) rk[sa[i]] = i;
    for(ll i = 1, j = 0; i <= n; hei[rk[i++]] = j)
        for(j = j ? j - 1 : j; s[i + j] == s[sa[rk[i] - 1] + j]; ++j);
}

ll f[N], id[N], ans[N][2];
ll siz[N], maxs[N], mins[N];

inline bool cmp(ll x, ll y){
    return hei[x] > hei[y];
}

inline ll find(ll x){
    return f[x] == x ? x : f[x] = find(f[x]);
}

inline void Union(ll x, ll y){
    ll k = hei[x];
    x = find(x), y = find(y);
    ans[k][0] += siz[x] * siz[y];
    ans[k][1] = max(ans[k][1], max(maxs[x] * maxs[y], mins[x] * mins[y]));
    mins[x] = min(mins[x], mins[y]);
    maxs[x] = max(maxs[x], maxs[y]);
    f[y] = x, siz[x] += siz[y];
}

inline void solve(){
    for(ll i = 1; i <= n; ++i)
        f[i] = i, siz[i] = 1, mins[i] = maxs[i] = a[sa[i]];
    for(ll i = 1; i <= n; ++i) Union(id[i], id[i] - 1);
}

signed main(){
    scanf("%lld%s", &n, s + 1);
    for(ll i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    build_sa();
    for(ll i = 1; i <= n; ++i)
        id[i] = i, ans[i][0] = 0, ans[i][1] = -1e18;
    sort(id + 1, id + 1 + n, cmp);
    solve();
    for(ll i = n - 1; i >= 0; --i){
        ans[i][0] += ans[i + 1][0];
        ans[i][1] = max(ans[i][1], ans[i + 1][1]);
    }
    for(ll i = 0; i < n; ++i)
        printf("%lld %lld\n", ans[i][0], !ans[i][0] ? 0 : ans[i][1]);
    return 0;
}