CF587F Duff is Mad

暴力就是每个串都在自动机上跑一下。

稍微优化一下就是之前跑过的就不跑了。

在跑的时候把所有的答案都记录下来。

之后考虑进行根号分治。

如果说当前串的长度 $> \sqrt n$ 那么出现次数肯定 $< \sqrt n$。我们直接进行暴力跑,是可以接受的。

对于长度 $< \sqrt n$ 的串,我们考虑建立 $fail$ 树。之后从根节点开始遍历,对于每一个结束标记都放到主席树里面去。

对于查询的时候从上到下走自动机上的节点加上对应的贡献即可。

使用主席树维护每一个节点的前缀和即可。

省空间。

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
#include <bits/stdc++.h>
using namespace std;

//#define Fread
//#define Getmod

#ifdef Fread
char buf[1 << 21], *iS, *iT;
#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
#define getchar gc
#endif // Fread

template <typename T>
void r1(T &x) {
x = 0;
char c(getchar());
int f(1);
for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
for(; '0' <= c && c <= '9';c = getchar()) x = (x * 10) + (c ^ 48);
x *= f;
}

#ifdef Getmod
const int mod = 1e9 + 7;
template <int mod>
struct typemod {
int z;
typemod(int a = 0) : z(a) {}
inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);}
inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);}
inline int mul(int a,int b) const {return 1ll * a * b % mod;}
typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));}
typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));}
typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));}
typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;}
typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;}
typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;}
int operator == (const typemod<mod> &x) const {return x.z == z;}
int operator != (const typemod<mod> &x) const {return x.z != z;}
};
typedef typemod<mod> Tm;
#endif

template <typename T,typename... Args> inline void r1(T& t, Args&... args) {
r1(t); r1(args...);
}

//#define int long long
const int maxn = 1e5 + 5;
const int maxm = maxn << 1;
int tot(0);
int t[maxn][26], fail[maxn];
string c[maxn];
int len[maxn];
int point[maxn];
vector<int> pt[maxn];
int totlen(0);
void Insert(int i) {
cin >> c[i];
len[i] = c[i].size(), totlen += len[i];
int now(0);
for(int j = 0; j < len[i]; ++ j) {
int x = (c[i][j] - 'a');
if(!t[now][x]) t[now][x] = ++ tot;
now = t[now][x];
}
pt[now].push_back(i); point[i] = now;
}

void build() {
static queue<int> q;
while(!q.empty()) q.pop();
for(int i = 0; i < 26; ++ i) if(t[0][i]) q.push(t[0][i]), fail[t[0][i]] = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < 26; ++ i) {
if(t[u][i]) fail[t[u][i]] = t[fail[u]][i], q.push(t[u][i]);
else t[u][i] = t[fail[u]][i];
}
}
}

int head[maxn], cnt;
struct Edge {
int to, next;
}edg[maxn << 1];
void add(int u,int v) {
// printf("(%d, %d)\n", u, v);
edg[++ cnt] = (Edge) {v, head[u]}, head[u] = cnt;
}

struct Query {
int l, r, id, k, opt;
int operator < (const Query &z) const {
return opt == z.opt ? k < z.k : opt > z.opt;
}
}q[maxn];

long long ans[maxn];
struct Node {
int l, r;
long long val;
}tr[maxn * 40];
int rt[maxn], ct(0);
struct Seg {
#define ls tr[p].l
#define rs tr[p].r
#define mid ((l + r) >> 1)
void Insert(int &p, int pre,int l,int r,int pos) {
p = ++ ct;
tr[p] = tr[pre];
++ tr[p].val;
if(l == r) return ;
if(pos <= mid) Insert(ls, tr[pre].l, l, mid, pos);
else Insert(rs, tr[pre].r, mid + 1, r, pos);
}
int ask(int p,int l,int r,int pos) {
if(!pos) return 0;
if(l == r) return tr[p].val;
if(pos <= mid) return ask(ls, l, mid, pos);
else return tr[ls].val + ask(rs, mid + 1, r, pos);
}
}T;

int n, m;

void dfs(int p) {
for(int i = head[p];i;i = edg[i].next) {
int to = edg[i].to; rt[to] = rt[p];
for(int j = 0; j < pt[to].size(); ++ j) T.Insert(rt[to], rt[to], 1, n, pt[to][j]);
dfs(to);
}
}

long long sum[maxn];

void Dfs(int p) {
for(int i = head[p];i;i = edg[i].next) {
int to = edg[i].to;
Dfs(to); sum[p] += sum[to];
}
}

long long pre[maxn];

void Solve(int i) {
for(int j = 0, now = 0; j < len[i]; ++ j) {
int x = c[i][j] - 'a';
now = t[now][x];
++ sum[now];
}
}

signed main() {
// freopen("S.in", "r", stdin);
// freopen("S.out", "w", stdout);
int i, j;
r1(n, m);
for(i = 1; i <= n; ++ i) Insert(i);
build();
totlen = sqrt(totlen);
for(i = 1; i <= m; ++ i) {
int l, r, k;
r1(l, r, k);
q[i] = (Query) {l, r, i, k, (bool)(len[k] > totlen)};
}
sort(q + 1, q + m + 1);
for(i = 1; i <= tot; ++ i) add(fail[i], i);
dfs(0);
for(i = 1; i <= m; i = j + 1) {
if(q[i].opt == 0) break;
j = i;
for(; j < m && q[j + 1].k == q[i].k && q[j + 1].opt == 1; ++ j) ;
memset(sum, 0, sizeof(sum));
Solve(q[i].k), Dfs(0);
for(int k = 1; k <= n; ++ k) pre[k] = pre[k - 1] + sum[point[k]];
for(int k = i; k <= j; ++ k) ans[q[k].id] = pre[q[k].r] - pre[q[k].l - 1];
}
for(; i <= m; ++ i) {
for(int j = 0, now = 0; j < len[q[i].k]; ++ j) {
int x = c[q[i].k][j] - 'a';
now = t[now][x];
ans[q[i].id] += T.ask(rt[now], 1, n, q[i].r) - T.ask(rt[now], 1, n, q[i].l - 1);
}
}
for(i = 1; i <= m; ++ i) printf("%lld\n", ans[i]);
return 0;
}