Suffix Array.

反正最近也没什么状态, 就开始浩浩荡荡地补题解吧.

Description

给一个字符串. 定义$R$相似为从两个不同位置开始的后缀的LCP长度. 同时这两个后缀也是$0, 1, \ldots , R-1$相似的.

每个位置有一个权值$a_i$, 选择两个位置$i,j$将获得$a_i \times a_j$的权值.

求对于每个$R=0,\ldots,n-1$, 选出位置的权值最大值和方案数.

Solution

既然相似度可以缩小, 那么我们就按LCP长度降序排序, 依次做, 这样后面的一定符合条件.

用并查集把两个后缀所属的集合连接起来, 那么$size$的乘积就可以累加到当前长度的答案里了.

需要注意的是, $size$相乘只考虑了当前长度, 合并前的用于更长情况的答案也应该累加进来, 最后我们要做一个后缀和.

然后关于最大权值有一点注意, 因为有负权值, 所以要同时记并查集最小值, 用多种方式更新答案.

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#pragma GCC diagnostic ignored "-Wchar-subscripts"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 3e+5 + 5;

int n;
ll a[maxn], mn[maxn], mx[maxn], siz[maxn], ans[maxn], val[maxn];
int f[maxn];

struct node {
  int len, idx;
  bool operator < (const node &rhs) const {
    return len > rhs.len;
  }
}lcp[maxn];

struct SuffixArray
{
  char s[maxn];
  int sa[maxn], rk[maxn], tmp[maxn], ht[maxn];
  int bkt1[maxn], bkt2[maxn], fir[maxn], sec[maxn];

  void build() {
    for (int i = 1; i <= n; ++i) bkt1[s[i]]++;
    for (int i = 1; i < 128; ++i) bkt1[i] += bkt1[i - 1];
    for (int i = n; i; --i) 
      sa[bkt1[s[i]]--] = i;
    rk[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
    for (int len = 1; rk[sa[n]] < n; len <<= 1) {
      memset(bkt1, 0, sizeof bkt1);
      memset(bkt2, 0, sizeof bkt2);

      for (int i = 1; i <= n; ++i) {
        fir[i] = rk[i];
        bkt1[fir[i]]++;
        sec[i] = (i + len <= n ? rk[i + len] : 0);
        bkt2[sec[i]]++;
      }
      for (int i = 1; i <= n; ++i)
        bkt1[i] += bkt1[i - 1], bkt2[i] += bkt2[i - 1];
      for (int i = n; i; --i)
        tmp[bkt2[sec[i]]--] = i;
      for (int i = n; i; --i)
        sa[bkt1[fir[tmp[i]]]--] = tmp[i];
      rk[sa[1]] = 1;
      for (int i = 2; i <= n; ++i)
        rk[sa[i]] = rk[sa[i - 1]] + (fir[sa[i]] != fir[sa[i - 1]] || sec[sa[i]] != sec[sa[i - 1]]);
    }   

    for (int i = 1, j = 0; i <= n; ++i) {
      j = j ? j - 1 : 0;
      while (s[i + j] == s[sa[rk[i] - 1] + j]) j++;
      //printf("->%d %d\n", rk[i], j);
      ht[rk[i]] = j;
      lcp[rk[i]].len = j;
      lcp[rk[i]].idx = rk[i];
    }
  }
}SA;

int find(int x) {
  return (f[x] == x) ? x : (f[x] = find(f[x]));
}
void link(int x, int y) {
  siz[y] += siz[x];
  mn[y] = min(mn[y], mn[x]);
  mx[y] = max(mx[y], mx[x]);
  f[x] = y;
}
void solve() {
  memset(val, 0xcf, sizeof val);
  for (int i = 0; i <= n; ++i) f[i] = i, siz[i] = 1;
  for (int i = 1; i <= n; ++i) {
    mx[i] = mn[i] = a[SA.sa[i]];
    //printf("rk %d a %d\n", i, mx[i]);
  }
  sort(lcp + 2, lcp + 1 + n);
  for (int i = 2; i <= n; ++i) {
    int r = lcp[i].len, idx = lcp[i].idx, idx_ = idx - 1;
    //printf("calc %d rk %d and %d\n", r, idx, idx_);
    int fx = find(idx), fy = find(idx_);
    ans[r] += siz[fx] * siz[fy];
    //printf("%d\n", ans[r]);
    val[r] = max(val[r], max(mx[fx] * mx[fy], mn[fx] * mn[fy]));
    val[r] = max(val[r], max(mx[fx] * mn[fy], mn[fx] * mx[fy]));
    link(fx, fy);
  }
  for (int i = n - 2; i >= 0; --i) ans[i] += ans[i + 1], val[i] = max(val[i], val[i + 1]);
}

inline int rd() {
  register int x = 0, f = 0, c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return f ? -x : x;
}

int main() {
  n = rd();
  scanf("%s", SA.s + 1);
  SA.build();
  for (int i = 1; i <= n; ++i) a[i] = rd();
  solve();
  for (int i = 0; i <= n - 1; ++i) {
    if (!ans[i]) puts("0 0");
    else printf("%lld %lld\n", ans[i], val[i]);
  }
  return 0;
}