建出反串的 SAM，考虑其 parent tree。
发现一组满足条件的 $ A,B $，其对应的 \(A\) 和 \(AB\) 在树上必然有祖先关系，且根据原题定义满足如下条件：
\(A\) 的 \(endpos\) 集合不包含 \(B\) 的那部分，最大的一个位置必须小于 \(|AB|\)。且 \(endpos_{AB}\) 是 \(endpos_{A}\) 的一个后缀（因为是反串）。
那么类似于树链剖分，将每个点树上的儿子中 \(endpos_{son}\) 包含 \(endpos_u\) 中最大一个位置的儿子设为重儿子，则满足条件的 \(A,B\) 必然只会在重链上出现。
单独考虑每一条链。设 \(mx_i\) 表示 \(i\) 点轻儿子 \(endpos\) 的最大值。此时就是序列问题。
那么显然点对 \(i,j(i<j)\) 贡献答案，要满足 \(|AB|>\max_{k=i}^{j-1}(mx_k)\)。然后 \(j\) 这个点的 \(|AB|\) 长度有一个区间 \([l,r]\)，则接下来统计答案可以二分然后数据结构。
后面是简单的维护序列问题。
标签：制胡,AB,串题,endpos,反串,某个,mx From： https://www.cnblogs.com/infinities/p/17144278.html