UOJ Logo MatKave的博客

博客

标签
暂无

知识集合

2020-10-03 00:44:42 By MatKave

A test

点分树

点分树就是使每次分治时重心的关系变为一颗树,从每个连通块的重心向这个联通块去掉重心后,形成的子问题的重心连边

易知每个点都会在树上出现一次,也只会在树上出现一次,且树高不超过 $\log n$,每个点的子树就代表着这个点作为重心时,求解的联通块内的所有点

对于树上的每个节点,用一种数据结构维护它的子树的信息

每次修改时,从这个点的位置从下往上爬点分树,因为每个点在同一层不会属于两个联通块,所以这个点只会对 $\log n$ 个节点的信息产生影响

每次查询也是从下往上爬点分树,枚举子树重心 $u$,用类似点分治的做法,把 $x$ 到 $y$ 的信息拆为 $x$ 到 $u$,然后 $u$ 到 $y$

但这样可能算重,所以要容斥,一般开两个数据结构,分别维护 $x$ 的子树对于 $x$ 的信息,和 $x$ 的子树对于 $x$ 的父亲的信息

每次加上 $x$ 的子树对于 $x$ 的信息,去掉 $pre$(之前算过的子树)对于 $pre$ 的父亲(也就是 $x$ ) 的信息

AC自动机

首先AC自动机是基于字典树的,所以要把所有字符串插入字典树

然后在字典树上,要对每个节点 $rt$ 求出一个 $fail$ 指针,表示从根到 $rt$ 的路径上形成的字符串,它的最长后缀满足后缀在字典树上出现过,出现的最后一位为 $fail$

这个就类似于 KMP 的那个 Border 的定义,它的定义是 一个最长的后缀,满足后缀与前缀相同 ,这里只不过把一个串的定义扩展到了一些串上,但是有一个不同:$fail$ 指针指向的只是一个子串,它可能不是前缀

求 $fail$ 的方式是在字典树上 $bfs$,每次从一个父节点 $u$,向子节点 $v$ 转移,可以发现,$v$ 的所有后缀实际上都是 $u$ 的后缀加上一个字符 $c$

因为 $fail_u$ 对应的字符串和 $u$ 的一个后缀肯定都是相同的,那么 $u$ 的一个后缀加入一个字符后,若 $fail_u$ 的后一位也是 $c$,那么就可以直接让 $fail_u$ 向下移动,加入字符 $c$

如果不匹配,就要选择 $v$ 的一个更短的后缀了,那么实际上也就是选择 $u$ 的一个更短的后缀,满足它在树上出现过,且它的后一位可以为 $c$

实际上,次长后缀就是最长后缀的最长后缀,次次长后缀就是次长后缀的最长后缀……

所以我们可以不断向上跳 $fail$,这样一定满足现在的串与 $u$ 的一个后缀相同,然后就只需要看能不能接上字符 $c$ 了。

而我们是按照深度从小到大求出 $fail$ 的,所以向上跳的值一定已经是算出来的

接下来分析一下复杂度:对于每一条独立的链,因为每次只会向下走 $dep$ 次,所以也只能向上跳 $dep$ 次

所以复杂度为 $\sum\limits_{i = 1}^n dep_{leaf_i}$,可以认为就是 $\sum t_i$

另一种方法是,因为每次只需要求出 $fail_{i,j}$,表示在节点 $i$,下一个字符 $j$ 的 $fail$ 指针

然后用记忆化搜索的方式,就可以在 $n \times C$ 的复杂度内求出 $fail$ 指针,$C$ 为字符集大小

莫队二次离线

其实就是在移动指针,计算贡献的时候,进行差分,变为对于前缀的查询,最后扫一遍来回答所有问题

  • 区间逆序对

    • 从 $[l,r]$ 到 $[l,r + 1]$

      答案会增加 $[l,r]$ 中 $> a_{r + 1}$ 的数的数量

      差分为 $[1,r] - [1,l - 1]$

    • 从 $[l,r]$ 到 $[l - 1,r]$

      答案会增加 $[l,r]$ 中 $< a_{l - 1}$ 的数的数量

      还是差分为 $[1,r] - [1,l - 1]$

    • 从 $[l,r]$ 到 $[l,r - 1]$

      答案会减少 $[l,r - 1]$ 中 $> a_r$ 的数量

      $[1,r - 1] - [1,l - 1]$

    • 从 $[l,r]$ 到 $[l + 1,r]$

      答案会减少 $[l + 1,r]$ 中 $< a_l$ 的数量

      $[1,r] - [1,l]$

SA

设后缀 $[i,n]$ 的编号为 $i$

设 $sa_i$ 为排名为 $i$ 的后缀在原数组中的编号,$rk_i$ 为后缀 $[i,n]$ 的排名

具体做法就是进行倍增,每次对每个后缀的前 $len$ 位进行排序,然后通过前 $len$ 位的排序结果推出前 $2len$ 位的排序结果

假设我们现在知道了前 $len$ 位的 $sa,rk$,要比较两个后缀 $[i,n],[j,n]$ 的前 $2len$ 位

可以发现,根据字符串字典序的定义,若 $rk_i > rk_j$,即后缀 $i$ 的前 $len$ 位比后缀 $j$ 的前 $len$ 位大,那么后缀 $i$ 的前 $2len$ 位一定比后缀 $j$ 的前 $2len$ 位大,$rk_i < rk_j$ 同理

如果 $rk_i = rk_j$,实际上就是要比较后缀 $i,j$ 的 $[len + 1,2len]$ 位,实际上恰好就是比较 $rk_{i + len},rk_{j + len}$

也就是说,要对 $(rk_i,rk_{i + len})$ 进行双关键字排序

一个需要注意的点是,$rk$ 并不一定是一个 $[1,n]$ 的排列,如果两个后缀 $i,j$ 的前 $len$ 位完全相同,那 $rk_i = rk_j$ 也必须成立

$sa$ 数组在求出 $rk$ 后也可以推得

  • LCP 定理

    LCP,即最长公共前缀

    这里有两个重要的,关于LCP的定理:

    1. 对于 $i \le j \le k$,有:$LCP(sa_i,sa_k) = \min(LCP(sa_i,sa_j),LCP(sa_j,sa_k))$

    设 $p = \min(LCP(sa_i,sa_j),LCP(sa_j,sa_k))$,则 $p \ge LCP(sa_i,sa_j),LCP(sa_j,sa_k)$,即 $sa_i,sa_j$ 前 $p$ 位相同,$sa_j,sa_k$ 前 $p$ 位相同,可推得 $sa_i,sa_k$ 的前 $p$ 位也相同,即 $LCP(sa_i,sa_k) \ge p$。

    若 $LCP(sa_i,sa_k) = q > p$,则 $s_{sa_i + p} = s_{sa_k + p}$,又因为 $LCP(sa_i,sa_j),LCP(sa_j,sa_k)$ 中至少有一个值为 $p$,不妨设 $LCP(sa_i,sa_j)$ 值为 $p$

    所以我们可以知道 $s_{sa_i + p} \neq s_{sa_j + p}$,因为 $s_{sa_i + p} = s_{sa_k + p}$,所以 $s_{sa_j + p} \neq s_{sa_k + p}$,即 $LCP(sa_j,sa_k) = p$

    但是这样的话,因为 $sa_i + p,sa_k + p$ 位相同,$sa_i + p,sa_j + p$ 不同,所以 $sa_i,sa_k$ 肯定是更加“相似”的,不会中间顺序夹着一个 $sa_j$

    1. $LCP(sa_i,sa_j) = \min (LCP(sa_{k - 1},sa_k))(i < k \le j)$

    这个也很好理解,$LCP(sa_i,sa_j)$ 可以拆为 $\min(LCP(sa_i,sa_{i + 1}),LCP(sa_{i + 1},sa_j))$ 也就可以继续向下拆分,最后拆成这种形式

    然后我们就发现一个好:我们把 $LCP$ 转化为了一个 RMQ 问题,只需要想办法求出 $LCP(sa_{i - 1},sa_i)$ 就可以了

  • height 数组

    设 $height_i = LCP(sa_{i - 1},sa_i)$

    有一个定理:$height_{rk_i} \ge height_{rk_{i - 1}} - 1$

共 1 篇博客