[Codeforces587F] Duff is Mad

做法

考虑按串长根号分类。

对于串长大于 \(\sqrt n\) 的串,这样的串不会很多,枚举每个这样的串,用 AC 自动机统计其他每个串作为这个串子串出现的次数,算一下前缀和,然后回答一下关于这个串的所有询问。

对于串长小于等于 \(\sqrt n\) 的串,把询问 \([l,r]\) 拆成 \([1,r]\)\([1,l-1]\) 相减,然后从前往后扫每个前缀,回答与每个前缀相关的所有回答。在扫前缀的过程中,用一个 AC 自动机 \(\mathcal O(串长)\) 询问这个前缀中有多少个某个串的子串即可。那么只需要在 AC 自动机上实现一个 fail 树上的子树加(加入一个新的串),在 dfs 序上转为区间加,用分块做到 \(\mathcal O(\sqrt n)\) 区间加, \(\mathcal O(1)\) 单点询问就行了。

总复杂度为 \(\mathcal O(n\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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 100010;
const int sqr = int (sqrt(maxn));

char buf[maxn];

int n, q, ql[maxn], qr[maxn], qk[maxn];
ll ans[maxn];
string s[maxn];
vector<int> vq1[maxn], vq2[maxn];

namespace FQ {
// Block i : (i-1)*sqr + 1, i*sqr
int a[maxn], ba[maxn];
void add(int l, int r, int v) {
if (r-l+1 <= sqr) {
for (int i = l; i <= r; i++) {
a[i] += v;
}
return;
}
while (l % sqr != 1) a[l] += v, ++ l;
while (r % sqr != 0) a[r] += v, -- r;
int lb = (l-1)/sqr+1, rb = (r-1)/sqr+1;
for (int i = lb; i <= rb; i++) ba[i] += v;
}
int ask(int p) {
return a[p] + ba[(p-1)/sqr+1];
}
};

struct ACAuto {
vector<int> son[maxn];
int ch[maxn][26], fail[maxn], Q[maxn], tim;
int dfn[maxn], sz[maxn], ind[maxn], tot;
int sum[maxn];
ACAuto() {tot = 1, tim = 0;}
int addStr(string s) {
int cur = 1;
for (int i = 0; i < s.size(); i++) {
int x = s[i] - 'a';
if (!ch[cur][x]) ch[cur][x] = ++ tot;
cur = ch[cur][x];
}
return cur;
}
void dfs(int u) {
sz[u] = 1, dfn[u] = ++ tim;
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i];
dfs(v);
sz[u] += sz[v];
}
}
void build() {
int s = 0, t = 0;
fail[1] = 1;
for (int i = 0; i < 26; i++) {
if (ch[1][i]) {
fail[ch[1][i]] = 1;
Q[t++] = ch[1][i];
} else ch[1][i] = 1;
}
while (s < t) {
int u = Q[s++];
for (int i = 0; i < 26; i++) {
if (ch[u][i]) {
fail[ch[u][i]] = ch[fail[u]][i];
Q[t++] = ch[u][i];
} else ch[u][i] = ch[fail[u]][i];
}
}
for (int i = 2; i <= tot; i++) son[fail[i]].push_back(i);
dfs(1);
}
void dfs_sum(int u) {
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i];
dfs_sum(v);
sum[u] += sum[v];
}
}
} A;

ll cnt[maxn];

int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%s", buf);
s[i] = buf;
}
for (int i = 1; i <= q; i++) {
int l, r, k; scanf("%d%d%d", &l, &r, &k);
ql[i] = l, qr[i] = r, qk[i] = k;
if (s[k].size() > sqr) {
vq1[k].push_back(i);
} else {
vq2[l-1].push_back(-i);
vq2[r].push_back(i);
}
}
for (int i = 1; i <= n; i++) A.ind[i] = A.addStr(s[i]);
A.build();
for (int i = 1; i <= n; i++) {
FQ::add(A.dfn[A.ind[i]], A.dfn[A.ind[i]] + A.sz[A.ind[i]] - 1, 1);
for (int _ = 0; _ < vq2[i].size(); _++) {
int x = vq2[i][_], K = 1;
if (x < 0) K = -K, x = -x;
int cur = 1;
for (int j = 0; j < s[qk[x]].size(); j++) {
cur = A.ch[cur][s[qk[x]][j]-'a'];
ans[x] += K * FQ::ask(A.dfn[cur]);
}
}
}
for (int i = 1; i <= n; i++) {
if (s[i].size() > sqr) {
for (int j = 0; j <= n; j++) cnt[j] = 0;
for (int j = 1; j <= A.tot; j++) A.sum[j] = 0;
int cur = 1;
for (int j = 0; j < s[i].size(); j++) {
cur = A.ch[cur][s[i][j]-'a'];
++ A.sum[cur];
}
A.dfs_sum(1);
for (int j = 1; j <= n; j++) cnt[j] = A.sum[A.ind[j]];
for (int j = 1; j <= n; j++) cnt[j] += cnt[j-1];
for (int j = 0; j < vq1[i].size(); j++) {
int x = vq1[i][j];
ans[x] += cnt[qr[x]] - cnt[ql[x]-1];
}
}
}
for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
return 0;
}