「2025 ICPC 武汉邀请赛」J. Dictionary

发表于 分类于 本文字数： 1.6k 阅读时长 ≈ 6 分钟

Description

Link：QOJ 10745

给出一个长度为 nn 的字符串 SS。定义字典为 SS 的所有本质不同的子串构成的集合，定义单词为字典中的字符串。

有 QQ 次操作，每次操作会给出两个参数 l,rl, r，你将会在字典中，学习以 S[l:r]S[l : r] 为前缀的所有单词。每次操作结束后，你需要求出有多少个单词被你学习过。

数据范围：1≤n,Q≤2×1051 \leq n, Q \leq 2 \times 10^5，1≤l≤r≤n1 \leq l \leq r \leq n。

数据范围：44s / 10241024MiB。

唉西安邀请赛前，怎么这个题都不会做呢 … 简直烂完了 …

记录本题是因为，很少用 SA 的视角考虑这类问题，SA 相比 SAM 没那么直观。

Solution

算法一：SA

考虑建出 SA。对于排名为 i−1i - 1 和 ii 的两个后缀 sai−1,sai\mathrm{sa}_{i - 1}, \mathrm{sa}_i，其长度为 1∼height[i]1 \sim \mathrm{height}[i] 的前缀都是相同的，故后缀 sai\mathrm{sa}_i 相比后缀 sai−1\mathrm{sa}_{i - 1} 有 n−sai+1−height[i]n - \mathrm{sa}_i + 1 - \mathrm{height}[i] 个不同的前缀。记这些不同的前缀为后缀 sai\mathrm{sa}_i 表示的前缀。

在任意时刻，每个后缀表示的前缀，被学习过的部分一定构成一个后缀。于是考虑维护没被学习过的部分构成的前缀大小。

每次操作 l,rl, r，记 u=rklu = \mathrm{rk}_l。在 uu 两侧二分找到最大的区间 [L,R][L, R]，使得排名在该区间内的后缀与后缀 ll 的 LCP 均大于 r−l+1r - l + 1。此时注意到排名在 (L,R](L, R] 内的后缀，其 height 值均比 r−l+1r - l + 1 大，故这些后缀表示的前缀均要被学习（没学习过的部分全部清零）。特别地，排名为 LL 的后缀，其 height 值可能小于等于 r−l+1r - l + 1，要学习的部分是一个后缀（没学习过的部分与特定值取 min⁡\min）。

使用线段树维护没被学习过的部分，支持区间赋值与单点修改。

时间复杂度 O((n+Q)log⁡n)\mathcal{O}((n + Q) \log n)。

算法二：SAM

使用 SAM 做此题，就比 SA 直接得多了。对反串建 SAM，对于一个 SAM 上的状态表示的字符串集合，在任意时刻被学习过的部分一定构成一个后缀。于是考虑维护没被学习过的部分构成的前缀大小。

每次操作找到子串 S[l:r]S[l : r] 在 SAM 上的状态 uu（子串定位 trick）。在 parent 树上考虑，子树 uu 内的所有点（除了 uu），表示的字符串集合均要被学习（没被学习过的部分全部清零）。状态 uu 表示的字符串集合要被学习的部分是一个后缀（没被学习过的部分与特定值取 min⁡\min）。

在 dfs 序上使用线段树维护没被学习过的部分，支持区间赋值与单点修改。

时间复杂度 O((n+Q)log⁡n)\mathcal{O}((n + Q) \log 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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
#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 = 200100;
const int SIZE = N * 2;

int n, Q;
std::string str;

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();
    }

    int location[N];

    std::vector<int> son[SIZE];
    int anc[19][SIZE];

    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;
            }
        }

        location[i] = np;
    }

    void build_tree() {
        for (int i = 1; i <= NodeCount; i ++) {
            son[i].clear();
        }
        for (int i = 1; i <= NodeCount; i ++) {
            son[t[i].link].push_back(i);
            anc[0][i] = t[i].link;
        }
        for (int j = 1; j <= 18; j ++) {
            for (int i = 1; i <= NodeCount; i ++) {
                anc[j][i] = anc[j - 1][anc[j - 1][i]];
            }
        }
    }

    int find(int l, int r) {
        int p = location[l];
        for (int i = 18; i >= 0; i --) {
            if (t[anc[i][p]].maxl >= r - l + 1) {
                p = anc[i][p];
            }
        }
        return p;
    }
}

int dfsClock, dfn[SIZE], idx[SIZE];
int sze[SIZE];

void dfs_init(int u) {
    dfsClock ++;
    dfn[u] = dfsClock, idx[dfsClock] = u;
    sze[u] = 1;

    for (int v : SAM::son[u]) {
        dfs_init(v);
        sze[u] += sze[v];
    }
}

namespace SGT {
    struct node {
        s64 sum;
        int tag;
        void mk_tag() {
            sum = 0;
            tag = 1;
        }
    } t[SIZE * 4];

    void upd(int p) {
        t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
    }

    void spread(int p) {
        if (t[p].tag) {
            t[p * 2].mk_tag(), t[p * 2 + 1].mk_tag();
            t[p].tag = 0;
        }
    }

    void build(int p, int l, int r) {
        t[p].tag = 0;
        if (l == r) {
            int u = idx[l];
            t[p].sum = SAM::t[u].maxl - SAM::t[SAM::t[u].link].maxl;
            return;
        }
        int mid = (l + r) >> 1;
        build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
        upd(p);
    }

    void changePos(int p, int l, int r, int x, int y) {
        if (l == r) {
            t[p].sum = y;
            return;
        }
        spread(p);
        int mid = (l + r) >> 1;
        if (x <= mid) {
            changePos(p * 2, l, mid, x, y);
        } else {
            changePos(p * 2 + 1, mid + 1, r, x, y);
        }
        upd(p);
    }
    void changePos(int x, int y) {
        changePos(1, 1, dfsClock, x, y);
    }

    void changeRange(int p, int l, int r, int s, int e) {
        if (s <= l && r <= e) {
            t[p].mk_tag();
            return;
        }
        spread(p);
        int mid = (l + r) >> 1;
        if (s <= mid) {
            changeRange(p * 2, l, mid, s, e);
        }
        if (mid < e) {
            changeRange(p * 2 + 1, mid + 1, r, s, e);
        }
        upd(p);
    }
    void changeRange(int s, int e) {
        changeRange(1, 1, dfsClock, s, e);
    }

    s64 ask(int p, int l, int r, int s, int e) {
        if (s <= l && r <= e) {
            return t[p].sum;
        }
        spread(p);
        int mid = (l + r) >> 1;
        if (s <= mid && mid < e) {
            return ask(p * 2, l, mid, s, e) + ask(p * 2 + 1, mid + 1, r, s, e);
        }
        if (s <= mid) {
            return ask(p * 2, l, mid, s, e);
        } else {
            return ask(p * 2 + 1, mid + 1, r, s, e);
        }
    }
    s64 ask(int s, int e) {
        return ask(1, 1, dfsClock, s, e);
    }
}

s64 ans;

void op(int l, int r) {
    int p = SAM::find(l, r);

    if (sze[p] > 1) {
        ans += SGT::ask(dfn[p] + 1, dfn[p] + sze[p] - 1);
        SGT::changeRange(dfn[p] + 1, dfn[p] + sze[p] - 1);
    }

    int v = SGT::ask(dfn[p], dfn[p]), nv = r - l - SAM::t[SAM::t[p].link].maxl;
    if (v > nv) {
        ans += v - nv;
        SGT::changePos(dfn[p], nv);
    }
}

void work() {
    std::cin >> str, n = str.length();
    str = " " + str;

    SAM::init();

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

    SAM::build_tree();

    dfsClock = 0;
    dfs_init(1);

    ans = 0;
    SGT::build(1, 1, dfsClock);

    std::cin >> Q;

    while (Q --) {
        int l, r;
        std::cin >> l >> r;

        op(l, r);
        
        std::cout << ans << ' ';
    }

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

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

    int T;
    std::cin >> T;
    
    while (T --) {
        work();
    }

    return 0;
}

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