DAG链剖分

本文介绍的是针对于 SAM 上的 DAG 链剖分。

前置知识：SAM，树链剖分。

众所周知，我们可以快速在 SAM 上找到一个字符串，并且可以用一个节点在 parent 树上到根节点的路径表示一个字符串的所有后缀，但是无法很方便地表示一个字符串的所有前缀。

考虑一个字符串的所有前缀在 SAM 上对应的点是什么。

由于在一个字符串末尾添加字符相当于在 SAM 的 DAG 上走一条边，所以一个字符串的所有前缀对应了 DAG 上的一条路径。

考虑用类似树链剖分的思想，将 DAG 剖分成若干条重链，使得任意一条路径都可以拆分为 $O(\log n)$ 段重链。

设 $f_x$ 表示在 DAG 上以 $x$ 结尾的路径条数，$g_x$ 表示以 $x$ 开头的路径条数。

设 $F_x$ 表示 $x$ 连向的点中 $g$ 最大的那个，$G_x$ 表示连向 $x$ 的点中 $f$ 最大的那个，如果有最大值相同则任意取。

如果对于一条边 $x,y$，满足 $F_x=y$ 且 $G_y=x$，则将这条边设置为重边，其余边设置为轻边。

则任意一条路径都能被剖分为 $O(\log n)$ 条重链。

证明：

首先，$g_x=1+\sum\limits_{(x,y)\in E}g_y$。

若 $x$ 连向的点 $u$ 满足 $u\neq F_x$，则 $g_u\le g_{F_x},g_u<g_x-g_{F_x}$，所以 $g_u\le \frac {g_x}2$。

同理，若连向 $x$ 的 $u$ 满足 $u\neq G_x$，则 $f_u\le \frac{f_x}2$。

设 $p_x$ 表示 $x$ 这个前缀在 DAG 上对应的点，显然 $f_{p_x}$ 单调递增，$g_{p_x}$ 单调递减。

如果边 $p_x,p_{x+1}$ 是轻边，则要么 $f$ 至少乘 $2$，要么 $g$ 至少除以 $2$，又因为 SAM 的 DAG 上总路径条数是关于 $n$ 的多项式级别的，所以一条路径上不会有超过 $O(\log n)$ 条轻边。

具体实现可以直接通过二分哈希，实现 $O(\log^2n)$ 单次剖分。使用后缀数组求 lcp 可以做到 $O(\log n)$ 剖分。

有了这个做法后，我们可以做很多东西。

求区间最短 border、最长 border、border 个数。

考虑一个前缀是 border 的条件，也就是若 $S_{[l,i]}$ 是 $S_{[l,r]}$ 的后缀，则 $S_{[l,i]}$ 是 $S_{[l,r]}$ 的 border。

$A$ 是 $B$ 后缀相当于 $A$ 在 SAM 的 parent 树上是 $B$ 的祖先，所有 border 相当于 $S_{[l,r]}$ 的所有在 SAM 上对应的点是 $x$ 的祖先的前缀。

DAG 链剖分把 $S_{[l,r]}$ 所有前缀剖分成 $O(\log n)$ 个区间，查询变成了一个点祖先中所有编号在一个区间内的点，直接主席树即可。

把模式串在 SAM 上标出来，问题转化为求一个区间所有子串的权值和。

预处理出来每个点的祖先的权值和，DAG 链剖分后转化为区间和，直接求前缀和即可。

但是这样可能会多算在同一个节点上的情况，多算的贡献是一个二维数点，总复杂度 $O(n\log n+q\log^2 n)$。