BZOJ4199 「NOI2015」品酒大会

题解
后缀自动机

Description

给定字符串 $s$ ，和每个位置上的权值 $a_i$。对于每一个 $i \in [0, n)$ 求出有多少对 $(i, j)$ 满足 $LCP(sa_i, sa_j) \ge i$ 以及在这些 $(i, j)$ 中 $a_i \times a_j$ 最大是多少。$sa_i$ 表示从 $i$ 开始的后缀。

Solution

将原串反过来建 SAM 求得后缀树。考虑后缀树上一个节点 $u$ ，这个节点代表的子串是他的任意后代的后缀 。所以每两个在其子树中的点都会对第一问的答案造成贡献。只需要维护 right 集合的大小即可。

对于第二问，乘积最大有两种可能：一个是最大的两个相乘，一个是最小的两个相乘（负负得正）。所以只需要在 dfs 的时候顺便维护子树中的最大值和最小值，与子树合并的时候维护处答案。

最后再从后往前更新一遍答案。因为小的肯定包含在大的中，对第一问做加法，第二问取 max

具体看代码

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
82
83
84
85
86
87
88
89
/**
 * Author: AcFunction
 * Date:   2019-05-02 09:10:52
 * Email:  3486942970@qq.com
**/
 
#include <bits/stdc++.h>
#define ll long long 
 
using namespace std;
 
const int N = (int)1e6 + 10; 
const int INF = (int)1e9; 
 
int n, siz[N], o[N], w[N], mx[N], mn[N], dep[N]; 
char s[N];
ll ans1[N], ans2[N]; 
 
struct sam {
  int ch[26], len, fa; 
} a[N]; 
 
struct edge {
  int v; edge *next; 
} pool[N * 2], *h[N], *cur = pool; 
 
void addedge(int u, int v) {
  edge *p = cur++; p->v = v; 
  p->next = h[u], h[u] = p; 
}
 
int last = 1, tot = 1; 
 
void add(int c, int x) {
  int p = last, tp = ++tot; last = tp; w[tp] = o[x]; 
  a[tp].len = a[p].len + 1; siz[tot] = 1; 
  for(; p && !a[p].ch[c]; p = a[p].fa) 
    a[p].ch[c] = tp; 
  if(!p) {
    a[tp].fa = 1; 
  } else {
    int q = a[p].ch[c]; 
    if(a[q].len == a[p].len + 1) {
      a[tp].fa = q; 
    } else {
      int cl = ++tot; a[cl] = a[q]; 
      a[cl].len = a[p].len + 1; 
      a[q].fa = a[tp].fa = cl; 
      for(; p && a[p].ch[c] == q; p = a[p].fa)
        a[p].ch[c] = cl; 
    }
  }
}
 
void dfs(int u, int pre) {
  if(siz[u] == 1) {
    mx[u] = mn[u] = w[u]; 
  }
  for(edge *p = h[u]; p; p = p->next) {
    int v = p->v; if(v == pre) continue ; 
    dep[v] = dep[u] + 1; 
    dfs(v, u); 
    if(mx[u] != INF && mn[u] != INF)
      ans2[a[u].len] = max(ans2[a[u].len], max(1ll * mx[u] * mx[v], 1ll * mn[u] * mn[v])); 
    ans1[a[u].len] += 1ll * siz[u] * siz[v]; 
    siz[u] += siz[v]; 
    mx[u] = max(mx[u], mx[v]); 
    mn[u] = min(mn[u], mn[v]); 
  }
}
 
int main() {
  scanf("%d", &n); scanf("%s", s + 1); 
  for(int i = 0; i <= n; i++) ans1[i] = 0, ans2[i] = -(ll)9e18; 
  for(int i = 1; i <= n; i++) scanf("%d", &o[i]); 
  for(int i = n; i >= 1; i--) add(s[i] - 'a', i); 
  for(int i = 1; i <= tot; i++) 
    mx[i] = -INF, mn[i] = INF; 
  for(int i = 2; i <= tot; i++) addedge(a[i].fa, i); 
  dep[1] = 1, dfs(1, 0);
  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++) {
    if(ans1[i] == 0) ans2[i] = 0; 
    printf("%lld %lld\n", ans1[i], ans2[i]); 
  } 
  return 0; 
}