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$