题目回顾

我们有 $n$ 个字符串 $s_1, s_2, \dots, s_n$，以及 $q$ 次询问，每次询问给出 $l, r, k$，需要计算：

$$\sum_{j=l}^{r} \text{occur}(s_k, s_j)$$

其中 $\text{occur}(t, s)$ 表示 $t$ 在 $s$ 中作为子串出现的次数。

---

第一步：建立 Aho–Corasick 自动机

1. 建立 Trie

将所有字符串 $s_i$ 插入到 Trie 中，每个节点 $v$ 对应一个字符串（从根到该节点的路径）。

代码中：

TRIE[v][c]  // 从 v 经过字符 c 到达的子节点
end[v]      // 以节点 v 结尾的字符串编号

2. 构建失败指针 $f(v)$

对于每个节点 $v$，定义 $f(v)$ 为：从根到 $v$ 的路径字符串的最长真后缀，且该后缀是某个模式串的前缀（即在 Trie 中存在）。
如果 $v$ 是根，则 $f(\text{root}) = \text{root}$。

通过 BFS 构建：

• 对于根的直接子节点 $u$，$f(u) = \text{root}$。
• 对于一般节点 $v$，通过 $f(v) = \text{aut}[f(\text{parent})][c]$ 计算。

3. 构建自动机转移函数 $g(v, c)$

$g(v, c)$ 表示在节点 $v$ 读入字符 $c$ 后到达的状态：

• 如果 $TRIE[v][c] \neq -1$，则 $g(v, c) = TRIE[v][c]$。
• 否则，$g(v, c) = g(f(v), c)$。

代码中 aut[v][c] 就是 $g(v, c)$。

---

第二步：预处理每个字符串在自动机上的路径

对于每个字符串 $s_i$：

• 从根开始，依次通过 $g$ 转移。
• 每经过一个节点 $v$，就将 $i$ 加入 $tof[v]$（即原题解中的 $q[v]$）。
• 最终到达的节点 $last[i] = \text{end}[i]$ 加入 $ends[v]$（即原题解中的 $\text{end}[v]$）。

代码中：

tof[v].pb(x);   // 记录每个节点被哪些字符串经过
ends[v].pb(x);  // 记录哪些字符串以该节点结尾

---

第三步：转化为 C-Tree（Fail 树）

定义 $par[v] = f(v)$，对于非根节点，这形成一棵以根为根的树，称为 C-Tree（Fail 树）。

原问题转化为：

$$\text{ans}(l, r, k) = \sum_{v \in \text{subtree}(\text{last}[k])} \text{count}(v, [l, r]) $$

其中 $\text{count}(v, [l, r])$ 表示 $tof[v]$ 中值在 $[l, r]$ 内的元素个数。

---

第四步：根号分治

设 $B = 350$（或 $\sqrt{n}$），根据字符串 $s_k$ 的长度分类：

• 长串：$|s_k| \ge B$
• 短串：$|s_k| < B$

---

情况 1：长串 $|s_k| \ge B$

长串的数量很少，最多 $\frac{\sum |s_i|}{B} \approx \frac{10^5}{350} \approx 285$ 个。

对于每个长串 $i$，我们单独计算所有 $k = i$ 的询问。

方法：在 C-Tree 上 DFS，对于节点 $v$：

• 统计 $tof[v]$ 中 $i$ 出现的次数。
• 递归子树，得到子树内 $i$ 的总出现次数。
• 将该次数加到 $ends[v]$ 中所有字符串编号对应的 $ps$ 上。

最后对 $ps$ 做前缀和，即可回答所有 $k = i$ 的询问的区间和。

代码中：

For(i,0,n) if((int)s[i].size() >= K) {
    fill(ps, ps + maxn, 0LL);
    dfs(root, i);
    For(i,1,maxn) ps[i] += ps[i-1];
    rep(j, queries[i])
        Q[j].ans += ps[Q[j].r] - (Q[j].l ? ps[Q[j].l-1] : 0LL);
}

复杂度：每个长串 DFS 一遍 C-Tree，总复杂度 $O(n \times \text{长串数}) = O(n \sqrt{n})$。

---

情况 2：短串 $|s_k| < B$

对于短串，我们采用另一种方法：在 C-Tree 上 DFS 一次，动态维护一个数组 $a$，支持：

• 单点加：increase(i, val)
• 前缀和：sum(i)

在 DFS 过程中：

• 进入节点 $v$ 时，对 $ends[v]$ 中的每个 $j$ 执行 increase(j, 1)。
• 对于 $tof[v]$ 中的每个 $i$，如果 $s_i$ 是短串，则遍历所有 $k = i$ 的询问，用当前的 sum(r) - sum(l-1) 累加答案。
• 递归子树。
• 退出节点 $v$ 时，撤销 increase 操作。

由于短串的 $tof[v]$ 总和为 $O(n)$，且每个短串对应的询问总数可能很多，但每个节点 $v$ 的 $tof[v]$ 中的短串被访问的次数等于其祖先数，总复杂度为 $O((n + q) \sqrt{n})$。

代码中：

inline void dfs(int v){
    rep(a, ::ends[v]) SQRT.add(a, 1);
    rep(i, tof[v]) if((int)s[i].size() < K) {
        rep(j, queries[i])
            Q[j].ans += SQRT.ask(Q[j].r) - SQRT.ask(Q[j].l - 1);
    }
    rep(u, adj[v]) dfs(u);
    rep(a, ::ends[v]) SQRT.add(a, -1);
}

这里 SQRT 是一个分块数据结构，实现 $O(1)$ 单点加和 $O(\sqrt{n})$ 前缀和，总复杂度 $O((n + q) \sqrt{n})$。

---

第五步：数据结构实现

分块实现：

struct sqrt_decomposition{
    ll sum[maxn] = {}, tot[K] = {};
    inline void add(int p, ll val){
        while(p < maxn && p % K)
            sum[p ++] += val;
        while(p < maxn){
            tot[p/K] += val;
            p += K;
        }
    }
    inline ll ask(int p){
        return (p < 0 ? 0 : sum[p] + tot[p/K]);
    }
}SQRT;

• add(p, val)：$O(1)$ 均摊。
• ask(p)：$O(\sqrt{n})$。

---

总时间复杂度

• 建自动机：$O(\sum |s_i| \times 26)$，可优化为 $O(\sum |s_i|)$。
• 长串处理：$O(n \sqrt{n})$。
• 短串处理：$O((n + q) \sqrt{n})$。

总复杂度 $O((n + q) \sqrt{n})$，在 $n, q \le 10^5$ 时可接受。

---

总结

本题的核心技巧：

1. Aho–Corasick 自动机 将字符串匹配转化为 Trie 和 Fail 树上的问题。
2. Fail 树 将子串出现次数转化为子树查询。
3. 根号分治 平衡长串与短串的处理，避免单次 $O(n)$ 操作。

最终代码通过离线处理，在 $O((n+q)\sqrt{n})$ 时间内解决所有询问。