题意
给你 \(n\) 个串 \(s_{1\cdots n}\) ，每次询问给出 \(l,r,k\) ，问在 \(s_{l\cdots r}\) 中出现了多少次 \(s_k\) 。
\(n,q,\sum|s|\le 10^5\)
分析
-
先建AC自动机的 \(fail\) 树， 我们考虑两种暴力：
- 将 \(l\) 到 \(r\) 中的每个串的末尾节点子树标记，查询 \(s_k\) 的所有节点 \(fail\) 树到根的路径和。
- 将 \(s_k\) 的每个节点的子树标记，查询 \(l\) 到 \(r\) 中的每个末尾节点的点权和。
-
发现这两种做法在不同的数据下有着不同的效果，考虑根号分治：
- 如果 \(|s_k|\le\sqrt n\) 采用第一种方式，差分查询，这样操作每个串的次数不超过 \(\sqrt n\) ，动态维护前缀和。
- 如果 \(|s_k|>\sqrt n\) 采用第二种方式，记录前缀和即可，这样的串不超过 \(\sqrt n\) 个。
-
我们发现，对于 \(dfs\) 序数组来说，修改次数是 \(O(n)\) 级别，但是查询次数却是 \(O(n\sqrt n)\) 级别的，能不能平衡两种操作时间复杂度呢？
考虑分块来维护前缀和，每个块维护一个加标记。这样修改变成了 \(O(\sqrt n)\) ，但是查询变成了 \(O(1)\) 。
总时间复杂度为 \(O(n\sqrt n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
template <typename T> inline void Max(T &a, T b){if(a < b) a = b;}
template <typename T> inline void Min(T &a, T b){if(a > b) a = b;}
const int N = 1e5 + 7;
int n, q, sz = 317, tim;
int L[N], R[N], in[N], out[N], ch[N][26];
char s[N];
namespace tr{
int edc;
int head[N];
struct edge {
int lst, to;
edge(){}edge(int lst, int to):lst(lst), to(to) {}
}e[N];
void Add(int a, int b) {
e[++edc] = edge(head[a], b), head[a] = edc;
}
void dfs(int u) {
in[u] = ++tim; go(u) dfs(v); out[u] = tim;
}
}
namespace ac {
int endp[N], fail[N], ndc;
int idx(char c) { return c - 'a';}
void ins(int a) {
L[a] = R[a - 1] + 1;
scanf("%s", s + L[a]);
R[a] = L[a] + strlen(s + L[a]) - 1;
int u = 0;
for(int i = L[a]; i <= R[a]; ++i) {
int c = idx(s[i]);
if(!ch[u][c]) ch[u][c] = ++ndc;
u = ch[u][c];
}
endp[a] = u;
}
void getfail() {
queue<int>Q;
for(int c = 0; c < 26; ++c) if(ch[0][c]) Q.push(ch[0][c]), tr::Add(0, ch[0][c]);
while(!Q.empty()) {
int u = Q.front();Q.pop();
for(int c = 0; c < 26; ++c) {
int &v = ch[u][c];
if(!v) { v = ch[fail[u]][c]; continue;}
fail[v] = ch[fail[u]][c];
Q.push(v);
tr::Add(fail[v], v);
}
}
}
}
struct data {
int l, r, k, id, opt;
bool operator <(const data &rhs) const {
return r < rhs.r;
}
}t[N << 1];
vector<data>G[N];
int qc, bl[N];//时间戳数组长度为tim
int Rp(int x){ return min(tim, x * sz);}
LL ans[N], sum[N], pre[N], add[400];
void mdf(int p, int v) {
if(p == tim + 1) return;
for(int i = p; i <= Rp(bl[p]); ++i) pre[i] +=v;
for(int i = bl[p] + 1; i <= bl[tim]; ++i) add[i] += v;
}
LL qry(int p) { return pre[p] + add[bl[p]]; }
void modify(int l, int r) { mdf(l, 1); mdf(r + 1, -1);}
LL query(int l, int r) { return qry(r) - qry(l - 1); }
void solve(int x) {
re(sum), re(pre), re(add);
int u = 0;
for(int i = L[x]; i <= R[x]; ++i) {
u = ch[u][ac::idx(s[i])];
mdf(in[u], 1);
}
for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + query(in[ac::endp[i]], out[ac::endp[i]]);
for(auto v: G[x]) {
ans[v.id] = sum[v.r] - sum[v.l - 1];
}
}
void Addstring(int x) {
int u = ac::endp[x];
modify(in[u], out[u]);
}
LL Substring(int x) {
int u = 0;LL ans = 0;
for(int i = L[x]; i <= R[x]; ++i) {
u = ch[u][ac::idx(s[i])];
ans += qry(in[u]);
}
return ans;
}
int main() {
n = gi(), q = gi();
rep(i, 1, n) ac::ins(i);
ac::getfail(), tr::dfs(0);
rep(i, 1, tim) bl[i] = (i - 1) / sz + 1;
rep(i, 1, q) {
int l = gi(), r = gi(), k = gi();
if(R[k] - L[k] + 1 <= sz) {
t[++qc] = (data){ 0, l - 1, k, i, -1 };
t[++qc] = (data){ 0, r, k, i, 1 };
}else
G[k].pb((data){ l, r, k, i, 1});
}
rep(i, 1, n) if(R[i] - L[i] + 1 > sz) solve(i);
re(pre), re(add);
sort(t + 1, t + 1 + qc);
for(int i = 0, j = 1; i <= n; ++i) {
if(i) Addstring(i);
for(; j <= qc && t[j].r == i; ++j) {
ans[t[j].id] += 1ll * t[j].opt * Substring(t[j].k);
}
}
rep(i, 1, q) printf("%lld\n", ans[i]);
return 0;
}