DDOSvoid's Blog

CF 587F Duff is Mad

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

题目描述

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

简要题意：给定 $n$​ 个字符串 $S_i$​，$m$​ 次询问 $S_l,S_{l+1},\cdots,S_r$​ 在 $S_k$​ 中出现的次数和

$n,m,\sum|S|\le 10^5$​

Solution

注意到一次询问相当于对于 $S_k$ 的每个前缀节点求其到根的链上有多少属于 $l$ 到 $r$ 的结束节点

或者反过来，对于 $l$ 到 $r$ 的每个结束节点求其子树内有多少 $S_k$ 的前缀节点

我们考虑按照 $S_k$ 的长度根号分治，以 $\sqrt L$ 为界限

对于长度大于 $\sqrt L$ 的 $S_k$​，我们考虑对于所有点求子树内有多少 $S_k$ 的前缀节点，这个离线下来可以做到单次 $O(L)$，总的时间复杂度就是 $O(L\sqrt L)$

对于长度小于等于 $\sqrt L$​ 的 $S_k$​，我们考虑对询问差分，然后考虑离线维护前 $i$​ 个串的结束节点的贡献，然后对于 $S_k$​ 的每个前缀节点求贡献即可，注意到这里有 $O(L)$​ 次区间修改，$O(L\sqrt L)$​ 单点查询，我们根号平衡一下即可做到 $O(L\sqrt L)$​

总的时间复杂度就是 $O(L\sqrt L)$，不过说实话感觉和带 $log$ 的差距不大

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
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#define maxn 100010
#define ll long long
using namespace std;

#define ch s[i] - 'a'
struct AC_automaton {
    int nxt[26], Nxt[26], cnt, fail;
} T[maxn]; int top = 1, rt = 1, id[maxn];
void insert(char *s, int k) {
    int now = rt, l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
        now = T[now].nxt[ch];
    } id[k] = now; 
} 

void init_fail() { // Trie 图
    queue<int> Q;
    for (int i = 0; i < 26; ++i) {
        int &u = T[rt].nxt[i];
        if (!u) { u = rt; continue; }
        T[u].fail = rt; Q.push(u); 
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); 
        for (int i = 0; i < 26; ++i) {
            int &v = T[u].nxt[i];
            if (!v) { v = T[T[u].fail].nxt[i]; continue; }
            T[v].fail = T[T[u].fail].nxt[i]; Q.push(v);
        }
    }
}

struct Block {
    int l[maxn], r[maxn], a[maxn], d[maxn], bl[maxn], blo, num, n;
    void init(int _n) {
        blo = sqrt(n = _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 update(int l, int r, int v) {
        add(l, v); if (r < n) add(r + 1, -v); 
    }
    void add(int x, int v) {
        for (int i = x; i <= r[bl[x]]; ++i) a[i] += v;
        for (int i = bl[x] + 1; i <= num; ++i) d[i] += v;  
    }
    inline int get_sum(int x) { return a[x] + d[bl[x]]; }
} block;

vector<int> G[maxn];
int in[maxn], out[maxn];
void Dfs(int u) {
    static int cnt = 0;
    in[u] = ++cnt; 
    for (auto v : G[u]) Dfs(v);
    out[u] = cnt;
}

int n, m, blo; ll ans[maxn];
char s[maxn]; int pos[maxn];

ll a[maxn];
void dfs(int u) {
    for (auto v : G[u]) dfs(v), a[u] += a[v];
}

struct node {
    int l, r, id; 
}; vector<node> C[maxn]; ll sum[maxn];
void solveB() {
    for (int o = 1; o <= n; ++o) {
        if (C[o].size() == 0) continue;
        for (int i = 1; i <= top; ++i) a[i] = 0; 
        for (int i = pos[o], now = rt; i < pos[o + 1]; ++i) {
            now = T[now].nxt[ch];
            ++a[now];
        } dfs(rt);
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[id[i]];
        for (auto t : C[o]) ans[t.id] += sum[t.r] - sum[t.l - 1];
    }
}

vector<pair<int, int>> A[maxn], B[maxn];
void solveS() {
    for (int o = 1; o <= n; ++o) {
        block.update(in[id[o]], out[id[o]], 1);
        for (auto [t, id] : A[o]) 
            for (int i = pos[t], now = rt; i < pos[t + 1]; ++i) {
                now = T[now].nxt[ch];
                ans[id] += block.get_sum(in[now]);
            }
        for (auto [t, id] : B[o]) 
            for (int i = pos[t], now = rt; i < pos[t + 1]; ++i) {
                now = T[now].nxt[ch];
                ans[id] -= block.get_sum(in[now]);
            }
    }
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; blo = sqrt(n); 
    for (int i = 1; i <= n; ++i) {
        cin >> s + pos[i]; insert(s + pos[i], i);
        pos[i + 1] = pos[i] + strlen(s + pos[i]); 
    } init_fail();
    for (int i = 1; i <= top; ++i) G[T[i].fail].push_back(i);
    Dfs(rt); block.init(top);
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        if (pos[z + 1] - pos[z] > blo) C[z].push_back({ x, y, i });
        else A[y].emplace_back(z, i), B[x - 1].emplace_back(z, i);
    } solveB(); solveS(); 
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0; 
}