DDOSvoid's Blog

Luogu P5576 [CmdOI2019]口头禅

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

题目描述

https://www.luogu.com.cn/problem/P5576

简要题意：给定 $n$ 个只有 $01$ 的字符串以及 $m$ 次询问，每次询问 $[l,r]$ 的所有字符串的最长公共子串的长度

$n\le 2\times 10^4,m\le 10^5,L\le 4\times 10^5$

Solution

首先对于所有字符串构建广义后缀自动机

然后我们考虑离线后扫描线来求解询问，我们考虑右端点 $r$ 增加时的影响

我们将广义后缀自动机上所有属于字符串 $r$ 的子串的节点拿出来，注意到这是一个自然根号，节点总数为 $O(L\sqrt L)$

我们对于每个节点维护它向左最长连续到哪里，这样每次可以 $O(1)$ 维护

然后我们考虑如何回答询问，相当于有 $O(L\sqrt L)$ 次单点修改，$O(m)$ 次区间查询最大值，这个东西我们再做一次根号平衡，总的时间复杂度为 $O(L\sqrt L+m\sqrt 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
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#define maxn 400010
#define Maxn 800010
#define maxs 200
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

struct SAM {
    int l, L, nxt[2];
} T[Maxn]; int rt, top, last, f[Maxn];
void init_SAM() {
    for (int i = 1; i <= top; ++i) {
        T[i].L = T[i].l = f[i] = 0; 
        fill(T[i].nxt, T[i].nxt + 26, 0); 
    }
    rt = last = top = 1; 
    T[rt].L = T[rt].l = f[rt] = 0;
}

int extend(int p, int ch) {
    if (T[p].nxt[ch]) {
        int q = T[p].nxt[ch], nq;
        if (T[q].L - 1 == T[p].L) return q;
        nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
        memcpy(T[nq].nxt, T[q].nxt, sizeof T[q].nxt); 
        while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
        f[q] = nq; return nq; 
    }
    int np = ++top; T[np].L = T[p].L + 1; 
    while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
    if (!p) return (f[np] = rt, np); 
    int q = T[p].nxt[ch];
    if (T[q].L - 1 == T[p].L) f[np] = q;
    else {
        int nq = ++top; T[nq].L = T[p].L + 1; 
        f[nq] = f[q]; memcpy(T[nq].nxt, T[q].nxt, sizeof T[q].nxt); 
        while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
        f[np] = f[q] = nq; 
    }
    return np; 
}

void insert(char *s) {
    int l = strlen(s), p = rt; 
    for (int i = 0; i < l; ++i) p = extend(p, s[i] - '0');
}

struct Block {
    int n, num, blo, l[maxs], r[maxs], a[maxn], d[maxs], bl[maxn];
    
    void init(int _n) {
        n = _n; blo = sqrt(n); num = (n + blo - 1) / blo;
        for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
        for (int i = 1; i <= num; ++i) {
            l[i] = (i - 1) * blo + 1;
            r[i] = i * blo; 
        } r[num] = n; 
    }
    void clear(int x) { d[bl[x]] = a[x] = 0; } 
    void update(int x, int v) {
        d[bl[x]] = max(d[bl[x]], v);
        a[x] = max(a[x], v); 
    }
    int query(int L, int R) {
        int Bl = bl[L], Br = bl[R], res = 0; 
        if (Bl == Br) {
            for (int i = L; i <= R; ++i) res = max(res, a[i]);
            return res;
        }
        for (int i = Bl + 1; i < Br; ++i) res = max(res, d[i]);
        for (int i = L; i <= r[Bl]; ++i) res = max(res, a[i]);
        for (int i = l[Br]; i <= R; ++i) res = max(res, a[i]);
        return res; 
    }
} B;

int n, m, pos[maxn];
char s[maxn];

vector<pair<int, int>> A[maxn];
int vis[Maxn], l[Maxn];

int ans[maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; init_SAM();
    for (int i = 1; i <= n; ++i) {
        cin >> s + pos[i]; insert(s + pos[i]);
        pos[i + 1] = pos[i] + strlen(s + pos[i]); 
    }
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        A[y].emplace_back(x, i); 
    } B.init(n); 
    for (int i = 1; i <= n; ++i) {
        vector<int> vec, tmp;
        for (int j = pos[i], p = rt; j < pos[i + 1]; ++j)
            p = T[p].nxt[s[j] - '0'], vec.push_back(p);
        for (auto t : vec)
            while (t && vis[t] != i) {
                if (vis[t] != i - 1) l[t] = 0; 
                if (!l[t]) l[t] = i;
                if (l[t] < i) {
                    tmp.push_back(l[t]);
                    B.update(l[t], T[t].L);
                }
                vis[t] = i; t = f[t];
            }
        for (auto [l, id] : A[i]) ans[id] = B.query(1, l);
        for (auto t : tmp) B.clear(t); 
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n"; 
    return 0;
}