给定 (n) 个字符串 (S_1, S_2, dots, S_n)，有 (q) 次询问，每次询问 (S_l, S_{l + 1}, dots, S_r) 在 (S_k) 中的出现次数。
(n, sum|S|, q leq 10^5)。
这题正好是把 [Codeforces547E]Mike and Friends 的询问颠倒了一下。
同样的思路，建立 AC 自动机，每次询问相当于查询 (S_l, S_{l + 1}, S_r) 的子树内包含多少 (S_k) 的前缀。
还是将询问离线，拆成两个前缀和之差。
注意到有两种不同的修改和查询的方式：
- 直接处理所有询问，每次区间加一 (S_r) 的子树，对于每个 (S_k) 的前缀都单点查询。
- 对于同一个 (S_k)，一起处理它的询问。先将其所有前缀单点加一，然后再拓展 (S_r)，每次查询子树和。
然后发现，如果 (|S_k|) 都很小，那么第一种更好；如果 (|S_k|) 都很大，由于字符串总长的限制，字符串个数会很少，第二种更好。
因此用根号分治，设一个阈值，小的用第一种，大的用第二种。
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
typedef long long LL;
typedef std::pair<int, int> PII;
constexpr int N(1e5 + 5), S(400);
int n, m, cnt, ch[N][26], fa[N], pos[N];
std::vector<int> g[N];
int ins(const std::string &s) {
int o = 0;
for (char c : s) {
if (!ch[o][c - 'a']) ch[o][c - 'a'] = ++cnt;
o = ch[o][c - 'a'];
}
return o;
}
int in[N], out[N];
void dfs(int x) {
static int c = 0;
in[x] = ++c;
for (int y : g[x]) dfs(y);
out[x] = c;
}
void build() {
static int q[N], l, r;
q[l = r = 1] = 0;
while (l <= r) {
int o = q[l++];
if (fa[o] == o) fa[o] = 0;
for (int i = 0; i < 26; i++) {
(ch[o][i] ? fa[q[++r] = ch[o][i]] : ch[o][i]) = ch[fa[o]][i];
}
}
for (int i = 1; i <= cnt; i++) g[fa[i]].push_back(i);
dfs(0);
}
// FenwickTree
LL c[N];
inline void add(int p, int x) {
for (; p <= cnt + 1; p += p & -p) c[p] += x;
}
inline LL ask(int p) {
LL r = 0;
for (; p; p -= p & -p) r += c[p];
return r;
}
std::string s[N];
struct Query { int k, r, id, tp; };
LL ans[N];
std::vector<Query> q1, q2[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
std::cin >> s[i];
pos[i] = ins(s[i]);
}
build();
for (int i = 1; i <= m; i++) {
int l, r, k; std::cin >> l >> r >> k;
if (s[k].length() <= S) {
q1.push_back({ k, l - 1, i, -1 });
q1.push_back({ k, r, i, 1 });
} else {
q2[k].push_back({ k, l - 1, i, -1 });
q2[k].push_back({ k, r, i, 1 });
}
}
auto cmp = [](const Query &a, const Query &b) {
return a.r < b.r;
};
std::sort(q1.begin(), q1.end(), cmp);
for (int i = 0, t = 1; i < (int)q1.size(); i++) {
while (t <= q1[i].r) {
int k = pos[t++];
add(in[k], 1), add(out[k] + 1, -1);
}
int o = 0;
for (char c : s[q1[i].k]) {
o = ch[o][c - 'a'];
ans[q1[i].id] += q1[i].tp * ask(in[o]);
}
}
for (int k = 1; k <= n; k++) {
if (s[k].length() <= S) continue;
memset(c, 0, cnt + 2 << 3);
int o = 0;
for (char c : s[k]) {
o = ch[o][c - 'a'];
add(in[o], 1);
}
LL sum = 0;
int t = 1;
std::sort(q2[k].begin(), q2[k].end(), cmp);
for (auto &v : q2[k]) {
while (t <= v.r) {
int p = pos[t++];
sum += ask(out[p]) - ask(in[p] - 1);
}
ans[v.id] += v.tp * sum;
}
}
for (int i = 1; i <= m; i++) {
printf("%lld
", ans[i]);
}
return 0;
}