DAG 链剖分学习笔记

lzqy_

·

2023-11-24 10:51:59

·

个人记录

DAG 链剖分学习笔记

后三题是嘴巴的，有时间写。

算法刻画

顾名思义，即找到一种方式将 DAG 剖分成若干条重链，使得任意一条路径上的轻边个数在可接受范围内（类似于树剖）。

设 f_i 表示以 i 为终点的路径数，g_i 表示以 i 为起点的路径数。u\rightarrow v 为重边当且仅当 u 是 v 的入点中 f 最大的，且 v 是 u 的出点中 g 最大的。

两个 \max 的限制使得每个点的入度出度都 \le 1，肯定成链；每次跳轻边 f,g 中至少有一个值减半，使得路径上轻边个数为 O(\log V)。其中 V 是 DAG 上的路径条数。

应用

观察到 DAG 链剖分本质上是对一条路径的拍平，所以其发挥用处的前提是 DAG 上的每条边与路径都有含义。

目前唯一见到过的使用场景只有 SAM 的 DAG 中，通过 O(\log V) 条轻边的优良性质，可以快速定位任意子串在 DAG 上的位置。

【UNR #6】Border 的第五种求法

定义一个字符串 t 的价值为 f_c，其中 c 是 t 在 S 中的出现次数。

$1\le |S|,q \le 5\times 10^5

本题的关键在于如何刻画子串 s_{[l,r]} 的 border。

考虑将 s_{[l,r]} 的 border 理解为 s_{[1,r]} 所有后缀与 s_{[l,n]} 所有前缀的交。前者是 Parent Tree 上一条到根的链，后者是 DAG 上一条从 1 出发的路径。

利用 DAG 链剖分，我们将路径拆分成 O(\log V) 段编号连续的区间，那么问题转化为给出 O(q\log V) 组询问，每次询问 \{1\rightarrow x\} 路径上且编号在 [l,r] 区间内点的权值之和，点 i 的权值为 f_{endpos(i)}（注意到一个节点中可能的 border 只有一个）。离线下来在树上跑 BIT 即可，略去。

还有一个小问题是如何跳重链。考虑对每一条重链对应的字符串维护哈希值，每次将 s_{[l,r]} 与重链上的区间二分匹配即可。

时间复杂度 O(n\log n\log V+n\log ^2n)。

[BJWC2018] Border 的四种求法

给出一个字符串 S，q 组询问，每次询问 S_{[l,r]} 的最长真 border。

与 【UNR #6】Border 的第五种求法 类似，将 s_{[l,r]} 对应的路径拆成 O(\log V) 个区间后，每个点的权值是固定的，在区间内形成公差为 1 的等差数列。我们钦定编号为 x 的节点权值 f_x=x，那么问题转化为给出 O(q\log V) 组询问，每次询问 \{1\rightarrow x\} 路径上且编号在 [l,r] 内区间点的权值最大值 +c。离线下来在树上维护一下线段树即可。

时间复杂度 O(n\log n\log V+n\log ^2 n)，做法与上一题极其类似。

Ж-function

给出一个字符串 S，q 组询问，每次询问 S_{[l,r]} 与其每个后缀的 \text{lcp} 之和。

1 \le |S|,q \le 2\times 10^5

一个经典结论是两个串的 \text{lcp} 等价于其在反串 Parent Tree 上 \text{LCA} 的深度。

对反串建出SAM，那么问题转化为求 s_{[l,r]} 与其每一段前缀对应节点的 \text{LCA} 深度之和。

前缀对应节点在 DAG 链剖分之后拍成 O(\log V) 个区间，这是经典问题，差分离线之后树剖加线段树即可。

注意当节点直接有祖先关系的时候要单独处理贡献。

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

你的名字

给出一个字符串 S，q 组询问，每次询问给出一个字符串 T，询问 T 有多少个本质不同的子串在 S_{[l,r]} 中没有出现过。

1 \le |S|,\sum|T|,q\le 5\times 10^5

一个观察是若 T' 在 S_{[l,r]} 中出现过，那么 T' 的所有子串都在 S_{[l,r]} 中出现过。这是有单调性的。

考虑枚举 T 子串的开头 L，那么问题转化为找到最大的 R，使得 T_{[L,R]} 在 S_{[l,r]} 中出现过。考虑对 S 建 SAM 后 DAG 链剖分，维护每个节点的 endpos 集合。先在 S 上找到 T_{[L,R]} 对应的节点，再观察存不存在一个合法的 endpos 时其在 S_{[l,r]} 内即可。

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

不知道能不能过，考虑进一步优化。

观察到该做法的瓶颈在于 DAG 链剖分内的二分还要查线段树上的 endpos。考虑先找到一个存在于整串的位置 T_{[L,R]}，此时真正合法的解位于 T_{[L,R]} 的前缀，即 1 到 T_{[L,R]} 链上的某个位置。先枚举在哪条重链，再在重链上二分，这样 3 个 \log 就没有套在一起了。

最终时间复杂度 O(n\log^2n+n\logn\log V)。