关于一个不使用并查集的做法

这大抵不算一个题解，所以直接发讨论了，因为可能常数上无法通过，只是一个数据结构的思想实验的记录。

一个不用并查集的做法的优势是，如果我们不使用线性并查集这种阴间东西的话，这个确实少了一个 alpha。

我们考虑还是序列中的每个数挂在它的因数上，然后考虑怎么 pop。我们在每一个点上开一个 $\frac{d(a)}{\log a}$ 叉的多叉线段树，由于 $d(a)$ 是关于 $a$ 多项式的，所以这个线段树在 $a\ge n$ 的时候是关于 $n$ 常数高的。我们在查询的时候每个节点暴力遍历所有的儿子，在有可能 pop 的子树内递归。这样 $O(n\log a)$ 次 pop，每次 pop 需要 $O(\frac{d(a)}{\log a})$ 的复杂度

这个做法直接暴力存多叉树空间比较爆炸，但是我们可以暴力用链表维护儿子，不需要保证任何的顺序，因为我们每次重新暴力遍历。

于是我们做到了更加严格的 $O(nd(a)+n\log n \log a)$