还是接着分块，之前写太多了，$\tt marktext$ 炸了。

Legendgod’s Blog

  • $\color{blue}\Delta$ 带插入全序集维护
题意：维护一个序列，支持（在指定元素后面）插入元素，询问两个元素的先后顺序。
  1. 平衡树

可以暴力维护，复杂度是 $O(\log n) - O(\log n)$ 。

或者说对于每个平衡树的每个节点钦定一个权值，每次插入的时候根据这样钦定的顺序每个点就有了一个权值，这样我们可以 $O(1)$ 比较。

但是这样对于深度的要求很高，我们用替罪羊树就行了 $O(\log n) - O(1)$。

  1. 块状链表

考虑上面这个 $O(1)$ 很妙能不能加强，我们还是考虑钦定权值，进行分块每块在 $[\log n, 2\log n]$ 的大小之间。

比较元素的时候优先比较块的位置，如果在同一块内在再比较块内的位置。

块内外都用钦定权值维护，但是块的元素数量比较多，如果一直搞链就寄了，所以需要使用平衡树维护，总共有 $\frac{n}{\log n}$ 个块，每次插入复杂度是 $O(\log n)$ 的，所以是 $O(n)$ 的。

考虑钦定块内元素的权值为前驱和后继权值的平均数。

我们一开始可以特别插入。

发现分裂总共需要 $O(\frac{n}{\log n})$ 次，均摊每次是 $O(1)$，每次查询是 $O(1)$ 的。

所以复杂度均摊 $O(1)$ 的。

根号分治 & 自然根号

  • $\color{blue}\Delta$ 根号分治

例 : 有若干数和为 $n$ ，则最多有 $\frac{n}{a}$ 个数字大于 $a$。

若对于某个数可以 $O(x)$ 处理，那我们就以 $O(xa)$ 的复杂度保证了其余数都 $\le a$。

看到和，先想能不能根号分治。

看到图先考虑生成树和点的度数。

  • 题意 : 维护一个 $n$ 个点 $m$ 条边的无向图，支持下列两种操作 :

  • 将点 $u$ 的权值 $+y$。

  • 查询与 $u$ 相连的点的权值和。

点的度数和是 $m$，考虑对于度数 $> \sqrt m$ 的点修改的时候计算贡献，然后对于另外的点暴力计算贡献。

题意：维护一个长度为 $n$ 的序列 $A$ 支持下列操作：

  • 单点修改。

  • 查询 $\sum_{i = 1} ^ n[i \equiv y \pmod x] A_i$。

考虑对于 $x > \sqrt n$ 的部分直接暴力做，小于的部分预处理。

  • $\color{blue}\Delta$ 和中的不同数

有若干个数和为 $n$，不同的数个数为 $\sqrt n$ 个。

$1 + 2 + 3 + \cdots+ x = O(x^2)$。

  • $\color{blue}\Delta$ 复杂度与 $\min$ 相关的询问

有 $m$ 个集合，大小分别为 $S_1, S_2, S_3, \cdots, S_m$ 设 $n = \sum_{i = 1} ^ m S_i$。

有 $q$ 次对询问，处理询问 $(x, y)$ 的复杂度为 $O(\min(S_x, S_y))$。

如果询问记忆化，总的复杂度为 $O(n\sqrt q)$。

将 $S$ 从大到小。

选择最大的 $q$ 个不同的询问，考虑复杂度的和为 $O(\sum_{i = 1}^{\sqrt q} S_i \times i)$。

考虑对于 $\sqrt q$ 个复杂度不同的询问，第 $i$ 个最多只能贡献 $i$ 次。

最差情况 $S$ 是 $O(\sqrt q)$ 个 $O(\frac{n}{\sqrt q})$，复杂度是 $O(n \sqrt q)$。

  • $\color{blue}\Delta$ 广义 SAM 上的一个算法

对于广义 $\tt SAM$ 定义 $siz_i$ 表示 $\tt parent$ 树子树内串的种类数。设模板串集合为 $S$，设 $n = \sum |S_i|$ ，有结论 $\sum_u siz_u$ 是 $O(n \sqrt n)$ 级别的。

考虑对于 $|S_i| \ge \sqrt n$ 的情况，其贡献最多是 $n$，因为串的数量少于 $\sqrt n$ 所以复杂度的贡献是 $O(n\sqrt n)$。

对于 $|S_i| < \sqrt n$ 的情况，其贡献最多为 $n \times \max(|S_i|)$，所以复杂度是 $O(n \sqrt n)$。

对于字符串的我们下个专题再说 /qd