题意
给定 n 个字符串 S_i 和一个字符串 T，和一个整数 K。
定义三元组 (l, r, k) 是好的，当且仅当 1 \le l \le r \le |T|,1 \le k \le K 且存在 k 个字符串 R_i，使得 R_1 + R_2 + \dots + R_k = T_{l \sim r}，且每个 R_i 都是某个 S_j 的前缀。R_i 可以为空。
求：
- 好的三元组数量；
- 对于每个 i，求满足 l \le i \le r 的好的三元组 (l,r,k) 数量。
第一问
首先有显然区间 DP。f(l,r,k) 表示 (l,r,k) 是否是好的三元组。
转移枚举 R_k 的左端点。复杂度四次方。
注意到有很显然的单调性 f(l,r,k) \le f(l,r+1,k)，于是转而记录 f(l,k) 表示所有好的三元组 (l, r, k) 中，r 的最大值是多少。
转移仍枚举 R_k 的左断点：
f(l,k) = \max_{i=l}^{f(l,k-1)+1}f(i,1)
答案是：
$$
\sum_{l=1}^{|T|}\sum_{k=1}^K f(l,k)-l+1
$$
显然再怎么优化 DP 都不可能低于这个平方的复杂度了。于是我们考虑观察一些其他的性质。
令 $g(l,k)$ 表示 $f(l,k)$ 的最优决策点（即 $f(l,k) = \max_{i=l}^{f(l,k-1)+1}f(i,1)$ 中最终选择的那个 $i$）。有 $f(l,k)=f(g(l,k),1)$。
注意到 $f(l,k-1) \le f(l,k)$。也就是 $f(l,k)$ 的决策区间（$[l,f(l,k-1)+1]$）是 $f(l,k+1)$ 的决策区间（$[l,f(l,k)+1]$）的前缀。又根据 $g(l,k)$ 是 $f(l,k)$ 的最优决策点，所以 $f(l,k+1)$ 的最优决策点 $g(l,k+1)$ 一定不小于 $g(l,k)$。
疯狂代入：
$$
f(l,k+1)=\max_{i=l}^{f(l,k)+1}f(i,1) = \max_{i=g(l,k)}^{f(l,k)+1}f(i,1) = \max_{i=g(l,k)}^{f(g(l,k),1)+1}f(i,1) = f(g(l,k),2)
$$
（第一步是 $f$ 的定义，第二步是上面说的决策点单调性，第三步是 $g$ 的定义，第四步是 $f$ 的定义。）
状态值相同，对应决策点也应相同。即 $g(l,k+1)=g(g(l,k),2)$。
（事实上，得到 $g(l,k+1)=g(g(l,k),2)$ 的思考过程不必如此复杂。直接从其定义入手，分析划分的 $R_{k-1},R_k,R_{k+1}$ 也能得到。）
考虑刻画这个东西。建一张 $x \to g(x,2)$ 的图。那么从 $g(l,k)$ 转移到 $g(l,k+1)$，相当于在图上从 $g(l,k)$ 走一步。这个步骤和 $k$ 无关。
那么在图上从 $l$ 开始走 $k-1$ 步到达的点就是 $g(l,k)$ 的值。
注意到转移中出现的环全是自环（因为 $g(x,2) \ge x$，右端点肯定不小于左端点），忽略它们，整张图是一张森林。也就是要求树上 $k$ 级祖先。
令 $h(l,k)$ 为树上 $l$ 的 $k$ 级祖先。那么答案为：
$$
\sum_{l=1}^{|T|}\sum_{k=0}^{K-1} f(h(l,\min(dep_l,k)),1)-l+1
$$
这里对 $dep_l$ 取了最小值的原因是考虑根的自环。
后面的 $-l+1$ 是平凡的。考虑快速求解：
$$
\sum_{l=1}^{|T|}\sum_{k=0}^{K-1} f(h(l,\min (dep_l, k)), 1)
$$
仍枚举 $l$。注意到 $\{h(l,\min (dep_l, k) \mid 0 \le k < K\}$ 是一条链，于是可以树上差分解决。
第一问做完啦啊哈哈哈哈哈哈哈哈。
## 第二问
$l \le i \le r$ 好难做的样子。考虑转化成总答案减去 $r < i$ 和 $l > i$ 的答案。
总答案是第一问。
$l > i$，即 $l \in [i+1,n]$。上面求解第一问时我们就是枚举的 $l$，所以直接维护一个后缀和即可。非常简单。
$r<i$，有点棘手。回到这个答案式子：
$$
\sum_{l=1}^{|T|}\sum_{k=0}^{K-1} f(h(l,\min(dep_l,k)),1)-l+1
$$
它的含义是，若左端点是 $l$，右端点 $r$ 至少为 $h(l,\min(dep_l,k))$ 时，$(l,r,k)$ 才是好三元组。
所以一个暴力的想法是枚举 $r \in [h(l,\min(dep_l,k))+1,n]$，将 $ans_r$ 加上 $r-l+1$。
差分维护这个东西。具体的，可以差分维护这样两个数组：
- $s0$：每次将 $[h(l,\min(dep_l,k))+1,n]$ 加 $1$；
- $s1$：每次将 $[h(l,\min(dep_l,k))+1,n]$ 加 $l$。
那么 $ans_r= s0_r (r+1) - s1_r$。
这样暴力枚举 $l,k$ 的复杂度是平方的。
怎么优化？仍枚举 $l$。仍然考虑 $\{h(l,\min (dep_l, k) \mid 0 \le k < K\}$ 是一条链。记录 $s0'_i$ 表示将要在 $s0_{i+1 \sim n}$ 全部加多少，$s1'_i$ 表示将要在 $s1_{i+1 \sim n}$ 全部加多少。这两个新数组可以树上差分维护。最后反推出 $s0,s1$ 数组即可。
第二问做完啦啊哈哈哈哈哈哈哈哈。
## 总结
很牛的 DP 优化题。从最开始的区间 DP，分析单调性质做到平方级别的复杂度。然后观察转移点的单调性建图，转化成树上问题。这种方式还是挺让人眼前一亮的。
反正爵士好题！