CF1098F Ж-function

MiniLong · 2025-11-28 11:48:19 · 题解

先对原串翻转，建出 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 的关系：

• 若 r - dep_r + 1 < l，此时 dep_i > dep_r 的 i 必定不会满足第一个限制，所以只用统计满足 l \le i - dep_i + 1 \le i \le r 的 i 即可。

• 若 r - dep_r + 1 \ge l，此时 dep_i \le dep_x 中不合法的 i 只需满足 i - dep_i + 1 < l，因为若 i>r 那么区间长度要大于 r - l + 1，就比 dep_r 大了。

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

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