最近试玩了一下一个叫做 Lean 的定理证明器，并尝试在里面证明了 Surreal 的主定理：一个树的集合是完备的当且仅当它能够生成每一棵高度为 $h$ 的树，其中 $h$ 为树的集合中包含的最高的树的高度。整个证明大概有 1k lines，花了大约 15 小时。

证明放在这里，欢迎大家来验证/基于里面的定理继续搞事

（正在考虑要不要冬令营来做一个关于定理证明器的 talk hh）

OI印象词征集！

在提到OI时您会有怎样的思绪呢？竞赛带给您怎样的回忆呢？这些偶尔浮现的碎片中倒映着历史，而我们正在寻找它们！问卷链接

By $\Sigma^*\text{Studio}$.

概述

原文发在 https://ljt12138.github.io/2019/12/01/k-sorter-problem/ ，如果有技术性问题可以在原文下评论（毕竟上github的频率比上uoj的频率高一点

k-sorter 问题指如何利用“给 k 个元素排序”这一基本操作，构造高效的排序算法。由于一个 k-sorter 可以由 $k\log k$ 次比较操作构造，而比较排序的时间复杂度下界是 $n\log n$，因此 k-sorter 问题的排序器使用次数下界（下称比较下界）为 $n\log n/k\log k$。我对这个问题的了解来自于清华大学邓俊辉老师的《数据结构》课程中的一道编程练习题（题目对应 $k=3$ 的情景），并将一个简单的做法（$n\log n/k$ 次比较的算法）出做了集训队作业题目[^1]。近期我对此问题又做了一些调查和探索，结论如下：

• 存在若干种比较次数在 $O(n\log n/k)$ 的确定性排序算法，包括两个比较简单的基于归并的算法；
• 存在期望 $O(n\log n/k\log k)$ 次比较的随机算法，这一算法思路简单，但分析稍加繁琐；
• 存在 $(n\log n/k\log k)$ 次比较的确定性算法，这一算法来自[^2].

两种简单算法

我们首先介绍两种比较次数为 $O(n\log n/k)$ 的简单算法。

算法1：二路归并

算法流程：考虑使用二路归并算法。首先将所有元素划分为等大的两部分递归排序，并在两序列末尾分别补上 $k/2$ 个无穷大 INF。接下来不断地如此做：在两个序列中分别选择 $k/2$ 个最小的数，将这些数排序，并将其中最小的 $k/2$ 个元素从队列中取出，直到除 INF 外的所有元素均被取出。

正确性：只需证明每次取出的 $k/2$ 个元素是整个序列最小的 $k/2$ 个元素即可，为此只需证明两序列最小的 $k/2$ 个元素的并包含了整个序列最小的 $k/2$ 个元素，而这是显然的。

比较次数：设 $T(n)$ 为比较次数，有 $T(n) = 2T(n/2) + O(n/(k/2))$，用主定理解得 $T(n) = O(n\log n/k)$。

算法2：$2^{k-1}$ 路归并

算法流程：首先将整个序列随意划分成 $2^{k-1}$ 个等大的部分递归排序，现在考虑如何合并这些序列。考虑建立一棵区间长度为 $2^{k-1}$ 的、维护区间最小值的线段树，其中位置 $i$ 维护划分成的第 $i$ 个序列中，未被取出的最小元素值。很明显，线段树的根节点便维护了所有 $2^{k-1}$ 路中所有元素的最小值（因为每个序列本身已经排序）。

考虑每次从线段树中取出最小元素以构成完整的、排序后的序列。不妨设当前全局最小值 $u$ 来自第 $i$ 个序列。在取出 $u$ 后，我们需要将线段树的位置 $i$ 更新为序列 $i$ 去掉 $u$ 后最小的元素。由于更新线段树上一个结点仅会影响这个结点到根上的所有结点 $i, parent(i), parent(parent(i)),\dots $，而这些结点的信息仅和 $$ i, brother(i), brother(parent(i)), brother(parent(parent(i)))\dots $$ 共 $k$ 个元素的相对大小有关，因此可以用一个 $k$-sorter 比较操作完成更新。

正确性：正确性是显然的。

比较次数：设 $T(n)$ 为比较次数，有 $T(n) = 2^{k-1}T(n/2^{k-1})+O(n)$，用主定理解得 $T(n) = O(n\log n/k)$。

类似快速排序的随机算法

算法流程

为了描述的方便不妨设我们拥有 $2k$-sorter 比较器。首先从所有元素中随机选出 $k$ 个支点，将他们用 1 次比较操作排序，并用 $O(n/k)$ 次比较操作将剩余 $n-k$ 个元素划分到这 $k$ 个元素之间，并递归对 $k+1$ 段进行排序。这一步可以通过每次将 $k$ 个元素和 $k$ 个支点共同排序来完成。

比较次数分析

由于分析过程复杂，这里仅列出一些关键的引理，证明的细节在附件 proof.pdf 中给出。

引理1： $$ \sum_{1\le i\le B} i{n-i-1\choose k-1} = {n\choose k+1} - \frac{Bk+n}{k+1}{n-B-1\choose k}. $$

引理2：当 $n>k>1$ 时，有 $$ \frac{1}{n\choose k}\left[\sum_{1\le i\le n-2}(n-1-i)i{n-i-2\choose k-2} + \sum_{1\le i\le n-1}2i{n-i-1\choose k-1} \right] = n-k. $$

引理3：算法的比较次数可以表示为

$$ T(n)=\frac{1}{n\choose k}\left[\sum_{0=i_0 \lt i_1\lt i_2\lt \dots\lt i_{d}\lt i_{d+1}=n+1}\sum_{1\le j\le d+1}T(i_j - i_{j-1}-1)\right] + O\left(\frac{n}{k}\right). $$

引理4： $$ T(n)=\frac{1}{n\choose k}\left[\sum_{1\le i\le n-2}(n-1-i)T(i){n-i-2\choose k-2} + \sum_{1\le i\le n-1}2 T(i){n-i-1\choose k-1}\right] + O\left(\frac n k\right). $$

引理5： $$ {n\choose k+1} - \frac{Bk+n}{k+1}{n-B-1\choose k} = \Theta\left({n\choose k+1}\right) $$

定理：多路快速排序算法的期望比较次数是 $O(n\log n/k\log k)$。

证明思路：考虑使用代入法，将 $cn\log n/k\log k$ 带入引理 4 并对和式进行估计。对于第二部分直接用 $\log n$ 作为 $\log i$ 的上界并用引理 2 计算，第一部分将和式分为 $[1, B]$ 和 $[B, n-2]$ 两部分，并分别用 $\log B$ 和 $\log n$ 作为 $\log i$ 的上界，取 $B = n/k$，利用引理 $1, 2, 5$ 进行估计。

注记

这一部分的分析是我自己折腾出来的，@AwD, @wmd, @WerkeyTom_FTD, @tqyaaaaang 等同学帮助 fix 了一些问题。

文献[^2]中给出了另外一种基于快速排序的实现：不断随机选择划分点，直到每一部分包含不超过 $2n/(k/2\ln k\log k)$ 个元素。

确定性算法

这一算法来自 [^2]

子算法 1

使用 $k$ 元比较器，在 $O(n/k)$ 次比较操作选出第 $i$ 大元素。

考虑将经典的 Median of medians 算法[^3]推广到 $k$ 元比较器上，这一点是容易的：将原先算法中分为 5 路变为 $k$ 路即可。

算法流程

算法分为四步。设 $a, b$ 为待取的常数。

1. 将序列随意划分为 $n/k$ 个长度为 $k$ 的链，并对每个链排序；
2. 从每个链中选出均匀的选出 $a$ 个元素，即选出排名为 $k/a, 2k/a, \dots$ 的元素，将所有链中选出的元素称为 $a$-points
3. 从所有 $a$-points 中均匀的选出 $b$ 个元素，称为 $b$-points
4. 将所有元素划分到 $b$-points 之间，递归给所有的段排序

算法分析

首先分析划分过程的复杂度。

1. 第一步需要 $n/k$ 次比较
2. 第二步不需要比较操作
3. 第三步通过连续 $b$ 次使用子算法，需要 $O(\frac{nab}{k^2})$ 次比较。
4. 第四步仅需要 $O(n/k)$ 次比较

取 $a = b = \frac {\sqrt k}{\log k}$，便可以将第三步的比较次数限制在 $O(n/k)$ 之内。

然后分析划分的平均程度。

引理：划分出的任何一段元素数量都不超过 $n(2/b+1/a)$。

证明：不妨将所有 $a$-points 从小到大列出，由于 $b$-points 是均匀选出的，任意两个 $b$-points 中均有 $O(na/(kb))$ 个 $a$-points。考虑原序列中，大小在某两个相邻的 $b$-points $b', b''$ 之间的元素个数。由于任何一个元素均在两个相邻的 $a$-points 之间，我们只需要考虑所有相邻的两个 $a$-points $a', a''$ 的情况。

1. 两个 $a$-points 至少有一者在 $b', b''$ 之间，由于其之间共有 $\frac{na}{kb}$ 个 $a$-points，这种情况仅有不超过 $\frac{2na}{kb}$ 对，因此这些 $a$-points 之间对应的原数组的元素个数之和为 $$ \frac{2na}{kb}\times \frac{k}{a} = \frac{2n}{b}. $$

2. $a' < b' < b'' < a''$，由于 $a'$ 和 $a''$ 在其对应的链上是连续的，因此在每一个链上至多有一对这样的 $a$-points，总的对数不会超过链的个数 $n/k$，之间的元素个数不会超过 $$ \frac{n}{k}\times \frac{k}{a} = \frac{n}{a}. $$

综上所述，任何两个 $b$-points 之间的元素个数都不超过 $n(2/b +1/a)$。

Q. E. D.

由于 $a = b=\sqrt k/\log k$，算法可以在 $O(n/k)$ 的时间复杂度内，将所有元素划分到 $b+1 = O(\sqrt k/\log k)$ 组中，并使得每组中元素都不超过 $3n/b$ 个元素。因此比较次数可以如下表示 $$ T(n) = \sum_{i=0}^{b} T(d_i) + O(n/k) $$

其中 $d_i$ 是第 $i$ 段中包含的元素个数，有 $d_i\le 3n/b$。那么用代入法就有 $$ \begin{equation} \begin{aligned} T(n) &\le \sum_{i=0}^b c\frac{d_i\log d_i}{k\log k} + c_1\frac{n}{k}\\ &\le \frac{c\log \frac{3n}{b}}{k\log k}\left(\sum_{i=0}^bd_i\right)+c_1\frac{n}{k}\\ &\le c\frac{n\log n}{k\log k}-c\frac{n\log \frac{b}{3}}{k\log k} +c_1\frac{n}{k}\\ &\le c\frac{n\log n}{k\log k} + \left(c_1\frac{n}{k}-c\frac{n(\frac{1}{2}\log k-\log\log k-\log 3)}{k\log k}\right)\\ &\le c\frac{n\log n}{k\log k} + \left(c_1\frac{n}{k}-cc_2\frac{n}{k}\right). \end{aligned} \end{equation} $$

取 $c = c_1/c_2$ 便能够使得归纳成立。

参考

[^1]: Uoj 题目 http://uoj.ac/problem/445

[^2]: Beigel R, Gill J. Sorting n objects with a k-sorter[J]. IEEE Transactions on Computers, 1990, 39(5): 714-716.

[^3]: Wiki https://en.wikipedia.org/wiki/Median_of_medians

在监考十二省联考的时候，我们发现排座位是一件非常麻烦的工作。由于主办单位需求的不同，例如成绩较好的靠前、同一学校的分开、成绩较好的分开、保证一定的随机性等等，我们需要用非常复杂的逻辑安排座位。事实上我们使用了一个简单的爬山，每次随机选择两个学生，如果交换可以使得代价函数降低就交换。

之后为了应付某图论应用技术报告我考虑了一个简化的问题，如果在 $n\times m$ 的网格图上分配座位，有 $n\times m$ 个选手来自 $k$ 个学校，其中第 $i$ 个学校有 $a_i$ 人，该如何分配座位使得任意相邻的两人都来自不同的学校。其中一个座位和其前后左右至多四个座位相邻。这个问题的证明是相对容易的，不过稍加改进便可以推广到任意维立方体的情景。

Theorem. 当且仅当 $\max\{a_i\}\le \lceil \frac{n\times m}{2} \rceil$，存在合法的座位安排方案。

Proof. $(\Leftarrow)$ 容易构造出使用尽可能多的 $1\times 2$ 的骨牌覆盖棋盘的方案，使得要么每个位置都被覆盖，要么仅存在一个单独的位置。整个棋盘被划分为了 $\lceil \frac{n\times m}{2} \rceil$ 组。如果一个学校人数超过一半，根据鸽巢原理，必然有一组中存在两个该学校的人，因而不存在合法的座位安排方案。

$(\Rightarrow)$ 我们希望说明一旦人数最多的学校人数不超过一半，就必然存在合法的座位安排方案。考虑直接构造。首先，若仅有两个学校，由于两者的人数都不超过 $\lceil \frac{n\times m}{2} \rceil$，因此他们必然分别具有 $\lceil \frac{n\times m}{2} \rceil$ 和 $\lfloor \frac{n\times m}{2} \rfloor$ 位选手。将棋盘黑白染色，我们可以将一个学校的人安排在黑色点，另一个学校的人安排在白色点，从而任意两个同校选手必然不相邻。

当学校个数超过 $2$ 时，我们先将所有选手分成人数相等（或差1）的两组，使得仅存在不超过一个学校，满足其选手被分到了两组中。若这样的学校不存在则证完了，否则不妨设这个学校编号为 $i$。由于我们可以将人数最多的学校分配到组 $A$，将人数第二多的学校分配到组 $B$，因此 $i$ 号学校至多是人数第三多的学校，从而其人数不超过 $nm/3$。另一方面，学校 $i$ 被分配到组 $A$ 的人数 $p$ 不超过 $nm/4$，被分配到组 $B$ 的人数 $q$ 也不超过 $nm/4$。

不妨设组 $A$ 有 $\lceil \frac{n\times m}{2}\rceil$ 人，组 $B$ 有 $\lfloor \frac{n\times m}{2} \rfloor$ 人，$(0,0)$ 是黑色点。我们只需将学校 $i$ 的 $p$ 人分配到黑色点，将另外 $q$ 人分配到白色点，使得任意两人不相邻，那么将 $A$ 中的其余人任意分配到黑色点上，$B$ 中的其余人任意分配到白色点上便完成了构造。

考虑这样的构造方案，我们首先从 $(0, 0)$ 开始，逐行逐列将 $p+q$ 人依次分配到黑色点中，然后将最后 $q$ 人向下移动一行。一旦满足：

$$ \frac{(n-1)m}{2} \ge p+q $$

这样的方案就一定可行。而这成立只需：

$$ \frac{(n-1)m}{2} \ge \frac{nm}{3} \iff n \ge 3 $$

根据对称性，一旦 $n\ge 3$ 或者 $m\ge 3$ 便立刻有合法的分组方案，因而也有构造方案。而 $n,m\le 2$ 的情景是平凡的，这就完成了证明。

Theorem. 当 $n\ge 144$ 或存在 $x_i\ge 3$ 时，对于 $x_1\times x_2\times x_3\times \dots \times x_n$ 的超立方体，存在合法的座位安排方案当且仅当：

$$ \max\{a_i\}\le \left\lceil \frac{\prod_i x_i}{2} \right\rceil $$

Proof. 稍加改进便可以知道，如果人数最多的学校人数超过一半仍然不存在方案，并且一旦某个 $x_i\ge 3$，之前的证明仍然成立。下面只需证明 $x_i = 2$ 的情况成立即可。

不妨将所有的位置映射到长度为 $n$ 的 $01$ 串，我们仍然希望将学校 $i$ 的 $p+q$ 个人合理安排，使得 $p$ 个人和另外 $q$ 个人不相邻。考虑这样的构造方案，将 $2^n$ 个不同的位置按照其中 $1$ 的个数分组，分为了大小分别为：

$$ {n\choose 0}, {n\choose 1}, \dots, {n\choose k}, \dots, {n\choose n} $$

的 $n+1$ 组。不失一般性我们设 $p\ge q$，于是前 $p$ 人从前向后选择具有偶数个 $1$ 的组，后 $q$ 人从后向前选择具有奇数个 $1$ 的组。我们只需说明，他们选择的组之中一定存在一个“分割”，保证他们不会选择相邻的组，从而更不会仅相差 $1$。下面用反证法。如若他们“触碰了”，即分配到 $A$ 组的 $p$ 个人占用了组：

$$ {n\choose 0}, {n\choose 2}, {n\choose 4}, \dots, {n\choose i} $$

而分配到 $B$ 组的 $q$ 个人占用了组：

$$ {n\choose i+1}, {n\choose i+3}, \dots {n\choose n-1} (or\ {n\choose n}) $$

那么一定有：

$$ \begin{align} \frac{2^n}{3}\ge p+q &\ge {n\choose 0} + {n\choose 2} + \dots + {n\choose i-1} + 1 + 1 + {n\choose i + 4} + {n\choose i + 6} + \dots + {n\choose n-1}(or\ {n\choose n})\\ &\ge {n\choose 0} + {n\choose 2} + \dots + {n\choose i-1} + 1 + 1 + {n\choose i + 5} + {n\choose i + 7} + \dots + {n\choose n}(or\ 0)\\ &\ge 2^{n-1} - 2\times \frac{2^n}{\sqrt{n+1}} \end{align} $$

要有这一点至少有：

$$ \frac{2^n}{3}\ge 2^{n-1} - 2\times\frac{2^n}{\sqrt{n+1}}\iff n\le 143 $$

thx

lkmcfj 提供了第一个定理证明中构造放置方案的方法（另一种简单的构造方案只能给出$m\ge 6$的界），CommonAnts 指出了第二个定理证明中构造放置的方案的方法。

hack

程序似乎写错了，现在 $n\le 12$ 这样的方案不一定能保证有解，但是原问题对 $n\le 4$ 都是有解的。

似乎后一个问题的证明完全有问题...找时间修一下吧orz

fix: 现在只能保证 $n\ge 144$ 是没有问题的..所以还是不知道小的情景怎么说明。

feat: 使用计算机改进第二个定理对组合数的估计可以说明，$n\ge 91$ 总是有解的。

Stage0

某天深夜水群的时候给小朋友普及Tarjan算法求LCA的时间复杂度，被老鸽们指正应当是$O(n+q)$而非$O(n+\alpha(q))$。最近阅读了一下wiki上指出的论文 https://core.ac.uk/download/pdf/82125836.pdf 学习了一下。

先放结论：RMQ问题和LCA问题的最优复杂度都是$O(n)-O(1)$的，线性复杂度的Tarjan需要做一些操作。

Stage1 : RMQ标准算法

通常我们所说的RMQ问题，即区间最值问题被描述为：给定一个数组和若干询问，每次询问一段区间中最小值/最大值。我们常常使用ST表或线段树来解决这样的问题，复杂度分别是$O(n\log n)-O(1)$和$O(n)-O(\log n)$。$O(f(n))-O(g(n))$表示预处理时间复杂度为$O(f(n))$，每次询问时间复杂度为$O(g(n))$。事实上，存在$O(n)-O(1)$的RMQ算法，这样的算法通常称为RMQ标准算法。

RMQ标准算法有三个步骤:

1. 建立序列的笛卡尔树，将RMQ问题转化成LCA问题
2. 通过树的欧拉序列，将LCA问题转化为±1 RMQ问题
3. 通过分块ST表解决±1 RMQ问题

为了方便，我们之后所有的讨论都为求区间最小值。

建立笛卡尔树

序列的笛卡尔树被定义为：最小值所在的位置作为根，其左侧区间的笛卡尔树作为左孩子，右侧区间的笛卡尔树作为右孩子的一棵树。假设我们拥有了一个序列的笛卡尔树，一个很明显的自顶向下寻找$[u, v]$区间最小值的算法如下：

1. 如果第一个点在当前节点左侧，第二个点在当前节点右侧，则根节点就是区间最小值
2. 如果在同一侧，则递归到该侧查询

我们事实上是在求$u,v$在笛卡尔树上的LCA。那么，$[u,v]$之间的区间最小值的位置，就是$u, v$在笛卡尔树上LCA所表示的位置。

笛卡尔树可以被线性的建立。我们每次在序列右端新增一个节点，并维护笛卡尔树最右端的点$rm$。对于每个节点$u$，我们维护其父亲$fa[u]$和其左右儿子$lc[u], rc[u]$。新增一个节点$nd$时，我们将其设为$rm$的右孩子。之后，利用平衡树的旋转操作，不断向上旋转，直到$nd$的父亲的值比其小为止，最后将$rm$设为$nd$。由于将$nd$向上旋转不会破坏序列的左右顺序，也不会破话除$nd, fa[nd]$两个节点之外父子的大小关系，最终得到的一定是原序列合法的笛卡尔树。

我们称$nd, rc[nd], rc[rc[nd]], ...$为笛卡尔树最右端的链，由于最右端的链长每次最多增加1，而每次向上旋转会使得其长度减小$1$，那么旋转的总次数是$O(n)$的，因而建立笛卡尔树的复杂度也是$O(n)$的。

转化为±1 RMQ问题

一个常见的求LCA的算法是转而求解树的欧拉序列上的RMQ问题。所谓欧拉序列，就是对树做dfs，每当访问一条边$(u,v)$时，就在序列上加入$v$。特别的，序列上一开始只有根节点。设每个节点$nd$出现的第一个位置为$pos[nd]$，那么，两个节点$u, v$的LCA，就是$[pos[u], pos[v]]$中最浅的节点。

欧拉序列良好的性质在于，任何两个相邻元素之间深度相差必然为$1$。那么问题便被转化为了，给定一个序列，任意两个元素之间相差为$1$，并给定若干个区间，求区间内最小的数。

±1 RMQ问题的线性解法

线性解决±1 RMQ问题的关键在于，由于相邻两个元素之差为1，那么长度为$n$的本质不同的数列只有$2^n$个。

考虑将序列按照长度为$\frac{\log(n)}{2}$分段，我们可以认为$\log(n)\le w$，$w$是计算机的字长（假设我们在随机储存器计算模型下）。长度为$\frac{\log(n)}{2}$的本质不同的数列只有$O(\sqrt{n})$个，我们可以枚举所有可能的情况，并枚举左右端点。这可以在$O(\sqrt{n}\log^2(n))$的时间复杂度内完成。一个数列长度为$n$的数列可以用二进制串编码，其第$j$位为$[a_j < a_{j+1}]$。

对于分成的$O\left(\frac{n}{\log(n)}\right)$段，使用ST表维护区间最小值。这样可以做到$O(n)$时间的预处理和$O(1)$时间的询问。

考虑一个区间询问$[u, v]$，可以看成一些整块和一些零散部分。对于整块，可以用ST表上$O(1)$询问最小值；对于零散部分，通过查表求出答案。这样，总共的询问时间复杂度是$O(1)$的，而所有预处理的复杂度都是$O(n)$的。因此，我们给出了$O(n)-O(1)$求解一般RMQ问题的解法。

Stage2 : 线性树上并查集

将Tarjan优化到线性的技术来源于线性树上并查集。树上并查集是并查集的一个特殊情况：给定一棵树，每次操作形如将一个节点合并到父亲，每次询问形如查询一个点已合并的祖先。

其一个更特殊的情景是当树退化成序列的情景：例如经典题目《花神游历各国》https://www.lydsy.com/JudgeOnline/problem.php?id=3211 的一个做法是利用并查集维护向右下一个不是$1$的元素。这可以看成一个以最右端节点为根的链上的并查集。

树上线性并查集的做法分为三步：

1. 将树分为大小为$O(b)$的块，且块的个数是$O(n/b)$的
2. 对于每种本质不同的块的本质不同的状态，预处理每个点的答案
3. 对块间维护并查集

将树分块

正如题目《王室联邦》https://www.lydsy.com/JudgeOnline/problem.php?id=1086 中指出，我们可以对树在线性时间内分块，使得每一个块的大小在$[b, 3b]$之间，且每一个块有一个“根”。满足每个块$B$都与其根联通，且$B$在其根的子树内。

使用一个dfs过程可以将树分块。在dfs所有子树后，我们将子树中剩下的节点（$\le b$个元素的零散块）合并，剩下至多一个零散块。这样可以保证，除了根节点可能有一个大小为$2b < size\le 3b$的块，其他的块大小都在$[b, 2b]$之间。

预处理

考虑本质不同的树至多有多少个，一棵树可以被父亲数组$parent[nd]$唯一确定，而$parent$数组可以被编码到长度$(b-1)\times \log b$，那么本质不同的树的上界就有$2^{(b-1)\log b}$种。对于每种本质不同的树，每一个节点可以被操作过，也可以没有被操作过，本质不同的状态有$2^b$个，那么每种本质不同的状态中每个节点的答案一共有：

$$2^{(b-1)\log b}\times 2^b\times b$$

如果我们取$b=\log\log n$，那么上式是$O(n)$的。

对块间维护并查集

我们对块间，即所有的“根”维护并查集。由于并查集的节点数只有$O(n/b)$，当我们取$b=\log\log n$时，总复杂度是$O(n/b\alpha(n)+q)=O(n+q)$的。

对于一个将节点合并到父亲的操作：可以$O(1)$修改块状态完成。

对于一个查询操作：如果当前块内已经合并到块的根了，向上查询。如果一个节点是某个块的根且合并到了其父亲，使用一个并查集合并上去。

这样，我们就在$O(n)-O(1)$的时间复杂度内解决了树上并查集问题！自然，Tarjan算法和花神游历各国的并查集部分都被加速到了线性。

Pollard-rho算法简要分析

标签（空格分隔）： 数论

概述

Pollard-rho算法是质因数分解的一种有效的蒙特卡洛算法，可以在期望$O(n^{1/4})$的复杂度内找到合数的一个因数。其核心思想就是随机的选取$x\lt n$，试图找到一个$x|n$。但直接利用反复随机的方法是行不通的，为了提高效率，Pollard-rho算法依靠“生日悖论”来找到一个因数。

“生日悖论”

生日悖论是指$k$个人两两生日不同的概率，随着$k$的增长下降的非常快。如果在$n$个数中随机选取$k$个，其两两之差全不为一个常数$c$的概率为$O(\frac{1}{n^{k^2}})$，因而如果通过两两之差去“碰”一个数，只需要期望$k = O(\sqrt n)$次。考虑如果一个数$n$的最小质因子是$O(\sqrt n)$，其小于$n$的倍数有$\Omega (\sqrt n)$个，如果我们随机选取$k$个数，两两作差寻找，碰到的概率为$\Omega(\frac{1}{(\sqrt n)^{k^2}})$，这样只需要期望$k = O(n^{1/4})$次就可以找到一个因数。

弗洛伊德判环

考虑如何在$O(1)$的附加空间内沿着环走一周，考虑用两个指针，一个每次移动一步，一个每次移动两步，其位置差每次增加$1$，直到位置差为环长即两个指针相遇，则他们刚好绕环一周，且他们取遍了每一种可能的位置差。

Pollard-rho算法

Pollard-rho算法的核心是构造一个“随机的”函数：

$$f(n) = f(n-1)^2+1$$

我们要用这个函数生成随机数去“碰”一个质因数的倍数，设这个集合为$S$。

注意到$f(x)$在模$n$意义下必然会形成一个环。考虑$f(x)-f(y)=f^2(x-1)-f^2(y-1) = (f(x-1)+f(y-1))(f(x-1)-f(y-1))$，有一个$f(x-1)-f(y-1)$因子。因而如果$f(x-1)-f(y-1)\in S$，就有$f(x)-f(y)\in S$。而根据欧几里得算法$\gcd(x, n)=\gcd(n,x\bmod n)$说明了如果一个数与$n$有公因子，那么模$n$后也有。因为形成环，立刻可以得到对于任意的$x_1, y_1, x_2, y_2$，如果满足$|x_1-y_1| = |x_2-y_2|$，即他们在环上的位置差相等，那么$|f(x_1)-f(y_1)|\bmod n\in S \iff |f(x_2)-f(y_2)|\bmod n\in S$。

换言之，环上的二元组被其之间的距离划分为了若干个$O(k)$个等价类，$k$为环长。那么这显然可以用弗洛伊德判环快速的完成，事实上，弗洛伊德判环每一次移动，都相当于进行了$O(k)$次两两比较。因而最终复杂度就是$O(n^{1/4})$。

算法流程就是，每次随机一个初始解$f(0)$，通过$x=f(x), y = f(f(y))$进行弗洛伊德判环，直到$\gcd(|x-y|, n)\ne 1$找到一个约数，或者$x=y$算法失败。如果找到一个约数，递归的分解两边。为了防止大素数导致时间退化，需要先用$Miller-rabin$素数测试判断是否是素数。

update: 5.21

复杂度分析被hack掉了...详情见评论orz

经过一些实验，看起来使用偶数次多项式同余做$f(x)$要比使用奇数次多项式优秀得多，前者约为$n^{1/4}$，后者约为$n^{1/2}$