「LOJ 6198」谢特

发表于 更新于 分类于 本文字数： 2.2k 阅读时长 ≈ 8 分钟

（老文章翻新，仅用于测试博客）

Description

Link：LOJ 6198

给出一个长度为 nn 仅包含小写字符的字符串 ss。

定义后缀 ii 的权值为 wiw_i，定义两个不同后缀 i,j(i≠j)i, j(i \neq j) 的贡献为 LCP(i,j)+(wixor⁡wj)\mathrm{LCP}(i, j) + (w_i \operatorname{xor} w_j)。其中 LCP(i,j)\mathrm{LCP}(i, j) 表示后缀 ii 和后缀 jj 的最长公共前缀长度。

你需要求出任意两个不同后缀 i,j(i≠j)i, j(i \neq j) 的贡献最大值。

数据范围：1≤n≤1051 \leq n \leq 10^5，0≤wi<n0 \leq w_i < n。

时空限制：11s / 512512MiB。

Solution

对于 LCP\mathrm{LCP} 问题，有一个观点：

  • 若使用 SA，就是将字符串问题转化成了序列问题（height 数组）。
  • 若使用 SAM，就是将字符串问题转化成了树上问题（parent 树）。

本题的结构相当广泛。许多题目都是类似的：使用 “height 数组” 或 “parent 树” 确定一个 LCP\mathrm{LCP} 大小，然后启发式合并处理二元关系。

SA 需要用 ST 表或笛卡尔树处理 height 数组，注意这里的笛卡尔树只需要处理 2∼n2 \sim n，计算答案的时候左端点需要减一；而 SAM 有个好处就是不用写 ST 表或笛卡尔树。

算法一：SA + 可持久化 0/1 trie

对字符串 ss 做一遍 SA，将 height 数组求出。

定义排名为 ii 的后缀权值为 wi′w'_i = wSAiw_{\mathrm{SA}_i}，故排名为 i,j(i≠j)i, j(i \neq j) 的后缀的贡献为

min⁡i<k≤j{heightk}+(wi′xor⁡wj′)\min\limits_{i < k \leq j} \{ \mathrm{height}_k \} + \left( w'_i \operatorname{xor} w'_j \right)

考虑最值分治。定义分治函数 solve(l,r)\mathrm{solve}(l, r) 表示计算 l≤i<j≤rl \leq i < j \leq r 情况下的答案。

取分治重心 pp 为区间 (l,r](l, r] 中 height\mathrm{height} 值最小的位置（使用 ST 表或笛卡尔树求出）。先考虑计算 l≤i<p≤j≤rl \leq i < p \leq j \leq r 情况下的答案，随后调用 solve(l,p−1),solve(p,r)\mathrm{solve}(l, p - 1), \mathrm{solve}(p, r) 即可。

此时 min⁡i<k≤j{heightk}=heightp\min\limits_{i < k \leq j} \{ \mathrm{height}_k \} = \mathrm{height}_p，故只需考虑 wi′xor⁡wj′w'_i \operatorname{xor} w'_j 的最大值。对于分治重心分出来的两个区间 [l,p−1],[p,r][l, p - 1], [p, r]，我们选择长度较小的一段区间，穷举该区间里的每一个点，使用可持久化 0/1 trie 求出该点与另一段区间的异或最大值。

倒过来看这个过程，每次枚举一个区间，总区间长度就至少乘二，这本质上是一个启发式合并（故称作启发式分裂）。

时间复杂度 O(nlog⁡2n)\mathcal{O}(n \log^2 n)。

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <bits/stdc++.h>

#define debug(a) std::cout << #a << "=" << (a) << ' '

using s64 = long long;
using u64 = unsigned long long;

/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int N = 100100;

int n;
std::string str;

int w[N];

int root[N];
namespace trie {
    int NodeCount;
    struct node {
        int trans[2];
        int cnt;
    } t[N * 32];

    void init() {
        NodeCount = 0;
    }

    void insert(int &p, int q, int d, int x) {
        p = ++ NodeCount, t[p] = t[q], t[p].cnt ++;
        if (d < 0) return;
        int v = x >> d & 1;
        insert(t[p].trans[v], t[q].trans[v], d - 1, x);
    }

    int ask(int p, int q, int d, int x) {
        if (d < 0) return 0;
        int v = x >> d & 1;
        if (t[t[q].trans[v ^ 1]].cnt - t[t[p].trans[v ^ 1]].cnt) {
            return ask(t[p].trans[v ^ 1], t[q].trans[v ^ 1], d - 1, x) + (1 << d);
        } else {
            return ask(t[p].trans[v], t[q].trans[v], d - 1, x);
        }
    }
    int ask(int l, int r, int x) {
        return ask(root[l - 1], root[r], 16, x);
    }
}

int ans;

namespace SA {
    int m;
    int sa[N], rk[N], height[N];
    int cnt[N], id[N], px[N];
    int tmprk[N * 2];

    int same(int x, int y, int k) {
        return tmprk[x] == tmprk[y] && tmprk[x + k] == tmprk[y + k];
    }

    void build() {
        if (n == 1) { sa[1] = rk[1] = 1, height[1] = 0; return; }

        for (int i = n + 1; i <= 2 * n; i ++) tmprk[i] = -1;

        m = 256;
        for (int i = 1; i <= n; i ++) rk[i] = str[i];

        for (int i = 1; i <= m; i ++) cnt[i] = 0;
        for (int i = 1; i <= n; i ++) cnt[rk[i]] ++;
        for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i --) sa[cnt[rk[i]] --] = i;

        for (int k = 1, p = 0; k < n; k <<= 1, m = p) {
            p = 0;
            for (int i = n - k + 1; i <= n; i ++) id[++ p] = i;
            for (int i = 1; i <= n; i ++)
                if (sa[i] > k) id[++ p] = sa[i] - k;
            
            for (int i = 1; i <= m; i ++) cnt[i] = 0;
            for (int i = 1; i <= n; i ++) cnt[px[i] = rk[id[i]]] ++;
            for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
            for (int i = n; i >= 1; i --) sa[cnt[px[i]] --] = id[i];

            for (int i = 1; i <= n; i ++) tmprk[i] = rk[i];

            p = 0;
            for (int i = 1; i <= n; i ++) rk[sa[i]] = same(sa[i - 1], sa[i], k) ? p : ++ p;

            if (p == n) break;
        }

        for (int i = 1, h = 0; i <= n; i ++) {
            if (h) h --;
            while (str[i + h] == str[sa[rk[i] - 1] + h]) h ++;
            height[rk[i]] = h;
        }
    }

    int rt;
    struct node {
        int lc, rc;
        int L, R;
    } t[N];

    int top, stk[N];
    void build_tree() {
        top = 0;
        for (int i = 2; i <= n; i ++) {
            t[i].lc = t[i].rc = 0, t[i].L = t[i].R = i;
        }

        for (int i = 2; i <= n; i ++) {
            int k = top;
            while (k && height[stk[k]] > height[i]) k --;

            if (k) t[stk[k]].rc = i;
            if (k < top) t[i].lc = stk[k + 1];

            stk[top = k + 1] = i;
        }
        rt = stk[1];
    }

    void solve(int p) {
        if (t[p].lc) solve(t[p].lc), chmin(t[p].L, t[t[p].lc].L);
        if (t[p].rc) solve(t[p].rc), chmax(t[p].R, t[t[p].rc].R);

        int l = t[p].L - 1, r = t[p].R;

        if (p - l < r - p + 1) {
            for (int i = l; i < p; i ++) {
                chmax(ans, height[p] + trie::ask(p, r, w[sa[i]]));
            }
        } else {
            for (int i = p; i <= r; i ++) {
                chmax(ans, height[p] + trie::ask(l, p - 1, w[sa[i]]));
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n;
    std::cin >> str, str = " " + str;

    for (int i = 1; i <= n; i ++) {
        std::cin >> w[i];
    }

    SA::build();

    trie::init();
    for (int i = 1; i <= n; i ++) {
        trie::insert(root[i], root[i - 1], 16, w[SA::sa[i]]);
    }

    SA::build_tree();

    ans = 0;
    SA::solve(SA::rt);

    std::cout << ans << '\n';

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/

算法二：SAM + 0/1 trie 合并

对字符串 ss 的反串建出 SAM，并求出 parent 树。

设后缀 ii 在反串建出的 SAM 上的代表节点为 eie_i，则 LCP(i,j)\mathrm{LCP}(i, j) 等于 parent 树上 LCA(ei,ej)\mathrm{LCA}(e_i, e_j) 的 maxl。

考虑遍历 parent 树。设当前节点为 uu，我们要计算两个后缀 i,ji, j 代表节点的 LCA\mathrm{LCA} 等于 uu 时的贡献。

依次遍历 uu 的所有儿子 vv，考虑计算后缀 ii 来自子树 uu，后缀 jj 来自子树 vv 情况下的贡献。此时 LCP(i,j)=maxlu\mathrm{LCP}(i, j) = \mathrm{maxl}_u，故只需要考虑 wixor⁡wjw_i \operatorname{xor} w_j 的最大值。我们选择较小的一棵子树，穷举该子树内的每一个终止节点，使用 0/1 trie 求出该点与另一棵子树内终止节点的异或最大值（过程需要用 0/1 trie 合并维护）。

这仍然是一个启发式合并。

时间复杂度 O(nlog⁡2n)\mathcal{O}(n \log^2 n)。

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <bits/stdc++.h>

#define debug(a) std::cout << #a << "=" << (a) << ' '

using s64 = long long;
using u64 = unsigned long long;

/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int N = 100100;
const int SIZE = N * 2;

int n;
std::string str;

int w[N];

int root[SIZE];
std::vector<int> g[SIZE];

namespace trie {
    int NodeCount;
    struct node {
        int trans[2];
    } t[SIZE * 32];

    int create() {
        int p = ++ NodeCount;
        t[p].trans[0] = t[p].trans[1] = 0;
        return p;
    }

    void init() {
        NodeCount = 0;
        for (int i = 1; i <= n * 2; i ++) {
            root[i] = 0;
            g[i].clear();
        }
    }

    void insert(int &p, int d, int x) {
        p = create();
        if (d < 0) return;
        int v = x >> d & 1;
        insert(t[p].trans[v], d - 1, x);
    }

    int merge(int p, int q) {
        if (!p || !q) return p ^ q;
        t[p].trans[0] = merge(t[p].trans[0], t[q].trans[0]);
        t[p].trans[1] = merge(t[p].trans[1], t[q].trans[1]);
        return p;
    }

    int ask(int p, int d, int x) {
        if (d < 0) return 0;
        int v = x >> d & 1;
        if (t[p].trans[v ^ 1]) {
            return ask(t[p].trans[v ^ 1], d - 1, x) + (1 << d);
        } else {
            return ask(t[p].trans[v], d - 1, x);
        }
    }
}

int ans;

namespace SAM {
    int NodeCount = 1, Last = 1;
    struct node {
        int trans[26];
        int link, maxl;
    } t[SIZE];

    int create() {
        int p = ++ NodeCount;
        for (int i = 0; i < 26; i ++) t[p].trans[i] = 0;
        t[p].link = t[p].maxl = 0;
        return p;
    }

    void init() {
        NodeCount = 0;
        Last = create();
    }

    void extend(int c, int i) {
        int p = Last,
            np = Last = create();
        
        t[np].maxl = t[p].maxl + 1;
        
        for (; p && t[p].trans[c] == 0; p = t[p].link) t[p].trans[c] = np;

        if (!p) {
            t[np].link = 1;
        } else {
            int q = t[p].trans[c];

            if (t[q].maxl == t[p].maxl + 1) {
                t[np].link = q;
            } else {
                int nq = ++ NodeCount; t[nq] = t[q]; t[nq].maxl = t[p].maxl + 1;
                t[np].link = t[q].link = nq;

                for (; p && t[p].trans[c] == q; p = t[p].link) t[p].trans[c] = nq;
            }
        }

        trie::insert(root[np], 16, w[i]);
        g[np].push_back(w[i]);
    }

    std::vector<int> son[SIZE];
    
    void build_tree() {
        for (int i = 1; i <= NodeCount; i ++) {
            son[i].clear();
        }
        for (int i = 2; i <= NodeCount; i ++) {
            son[t[i].link].push_back(i);
        }
    }

    void solve(int u) {
        for (int v : son[u]) {
            solve(v);

            if (g[u].size() < g[v].size()) {
                std::swap(g[u], g[v]);
                std::swap(root[u], root[v]);
            }

            for (int x : g[v]) {
                chmax(ans, t[u].maxl + trie::ask(root[u], 16, x));
                g[u].push_back(x);
            }
            root[u] = trie::merge(root[u], root[v]);
            g[v].clear();
        }
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n;
    std::cin >> str, str = " " + str;
    
    for (int i = 1; i <= n; i ++) {
        std::cin >> w[i];
    }

    trie::init();
    SAM::init();

    for (int i = n; i >= 1; i --) {
        SAM::extend(str[i] - 'a', i);
    }

    SAM::build_tree();

    ans = 0;
    SAM::solve(1);

    std::cout << ans << '\n';

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/