设 \(f(s,t)\) 表示串 \(s\) 在 \(t\) 中出现的次数。
首先把询问 \(\sum\limits_{i=l}^rf(s_i,s_k)\) 拆成 \(\sum\limits_{i=1}^rf(s_i,s_k)-\sum\limits_{i=1}^{l-1}f(s_i,s_k)\)，然后考虑如何算 \(\sum\limits_{i=1}^lf(s_i,s_k)\)。
建出 AC 自动机和 fail 树，现在有两种方式：（trie 树和 fail 树点集相同，边集不同）
- 在 trie 树上把 \(s_k\) 经过的节点都 +1，然后枚举 \(s_1\) 到 \(s_l\) 在 fail 树上的子树，统计子树上权值和。
- 先把 \(s_1\) 到 \(s_l\) 在 fail 树上的子树都 +1，然后统计 \(s_k\) 在 trie 树上经过的节点的权值和。
发现时间瓶颈在于 \(s_k\) 的长度，又因为 \(\sum\limits_{i=1}^n|s_i|\le10^5\)，考虑离线根号分治。
设阈值为 \(B\)，长度 \(\le B\) 的串用第二种，否则用第一种预处理。
具体实现上，对长度 \(\le B\) 的询问，我们把它拆开、离线、按 \(l\) 排序。加子树的操作可以转化为在 dfs 序上的区间加，询问是单点查值，树状数组即可；对长度 \(>B\) 的串，同样是把 trie 上的点拍到 dfs 序上，加完之后做前缀和，然后再枚举 \(l\)，做原顺序的前缀和。
假设 \(n,q,\sum\limits_{i=1}^n|s_i|\) 同阶，复杂度 \(O(\dfrac{n^2}B+Bn\log n)\)，当 \(B=\sqrt\dfrac n{\log n}\) 时最小，最小为 \(O(n\sqrt{n\log n})\)。
code:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s; i <= e; ++i)
#define per(i, s, e) for(int i = s; i >= e; --i)
#define F first
#define S second
//#define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> pii;
constexpr int N = 1e5 + 5, B = 100;
int n, Q, tr[N][26], fail[N], m, ed[N], dfn[N], sz[N], pre[N];
string s[N];
bool b[N];
vector<int> to[N];
vector<ll> ss[N];
ll ans[N];
struct Query {
int l, k, id;
Query(int L = 0, int K = 0, int i = 0):
l(L), k(K), id(i) {}
};
vector<Query> q;
#define lb(x) ((x) & -(x))
struct BIT {
int c[N];
void clear() { memset(c, 0, sizeof c); }
void add(int i, int v) {
for(; i <= m; i += lb(i)) c[i] += v;
}
int sum(int i) {
int res = 0;
for(; i; i -= lb(i)) res += c[i];
return res;
}
} bit;
void insert(string &s, int id) { // 插入 trie
int p = 0;
for(auto i : s) {
int c = i - 'a';
if(!tr[p][c]) tr[p][c] = ++m;
p = tr[p][c];
}
ed[id] = p;
}
void build() { // 构建 fail 树
queue<int> q;
rep(i, 0, 25) if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty()) {
int u = q.front(); q.pop();
rep(i, 0, 25) {
if(tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
else tr[u][i] = tr[fail[u]][i];
}
}
rep(i, 1, m) to[fail[i]].push_back(i);
}
void dfs(int p) { // 算出 fail 树上的 dfs 序和子树大小
static int ind = 0;
dfn[p] = ind++, sz[p] = 1;
for(auto i : to[p]) dfs(i), sz[p] += sz[i];
}
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> n >> Q;
rep(i, 1, n) {
cin >> s[i];
insert(s[i], i);
b[i] = s[i].size() > B;
}
build();
dfs(0);
rep(i, 1, n) if(b[i]) { // 预处理长度 >B 的
memset(pre, 0, sizeof pre);
int p = 0;
for(auto j : s[i]) p = tr[p][j - 'a'], ++pre[dfn[p]];
rep(j, 1, m) pre[j] += pre[j - 1];
ss[i].resize(n + 1);
rep(j, 1, n) ss[i][j] = pre[dfn[ed[j]] + sz[ed[j]] - 1] - pre[dfn[ed[j]] - 1] + ss[i][j - 1]; // 前缀和
}
rep(i, 1, Q) {
int l, r, k; cin >> l >> r >> k;
if(b[k]) ans[i] = ss[k][r] - ss[k][l - 1];
else {
q.emplace_back(l - 1, k, -i);
q.emplace_back(r, k, i);
}
}
sort(q.begin(), q.end(), [](Query &a, Query &b){ return a.l < b.l; });
int j = 0;
for(auto i : q) { // 离线处理长度 <B 的
while(j < i.l) {
++j;
bit.add(dfn[ed[j]], 1), bit.add(dfn[ed[j]] + sz[ed[j]], -1);
}
ll res = 0;
int p = 0;
for(auto j : s[i.k]) p = tr[p][j - 'a'], res += bit.sum(dfn[p]);
if(i.id < 0) ans[-i.id] -= res;
else ans[i.id] += res;
}
rep(i, 1, Q) cout << ans[i] << endl;
return 0;
}