CF1098F Ж-function

先对原串翻转，建出 SAM，设前缀 $i$ 在 SAM 的位置是 $pos_i$，要求的就是 $\sum\limits_{i=l}^r \min(i-l+1,dep_{lca(pos_i, pos_r)})$。

对后缀树重链剖分，把每个 $i$ 和询问的 $r$ 插到 $pos_x$ 祖先的 $O(\log n)$ 个重链中，对每个重链分别求答案，再减去来自同一轻子树的询问的前缀即可，那么现在就转成序列问题了。

为了方便，下设 $dep_i$ 为 $pos_i$ 在当前重链对应点的 dep。显然只需统计 $dep_{lca} \le i - l + 1$ 的所有 $dep_{lca}$ 之和与对应 $i$ 之和，稍微讨论一下偏序关系容易得到询问 $[l,r]$ 的贡献：

第二个限制是好求的，但第一个限制是三维的限制，直接做需要两个 $\log$，比较劣。

观察到 $[i - dep_i + 1, i]$ 的区间长度刚好是 $dep_i$，此时不妨讨论一下与 $[l,r]$ 长度与 $dep_r$ 的关系：

此时通过讨论即可成功把限制降为二维的，bit 统计即可。

复杂度 $O(n\log^2 n)$。