源码是冰封写的：

这里 ask 是一个递归查找的子程序，它递归寻找一个树状数组的 i == vec//i
并且
+ i == @i => @i=i
+ 否则，总之就是递归下去找 @@i 什么的，然后存下来结果（就是把这个节点直接重写了）

比如这里有一个小离散化的树

root=3
@1=3
@2=2
@3=1

我们去 ask 这个 3 (ask vec 3)，然后结果是：

l1: i=3, @i==1/=0, @3=rec 1
l2: i=1, @i==3/=1, @1=rec 3
leven: i=3
lodd: i=1...
这样的话就成环(cycle)了... 怪我的图没画好，可是如果没有环就是：

l1: i=3, @i==1/=0, @3=rec 1
l2: i=1, @i==2/=1, @1=rec 2
l3: i=2 @i==2==2, 2

这就是在找... 爸爸的爸爸的... 等于爸爸或者、爸爸的爸爸就是爸爸自己（root）？只不过是离散化的版本？

原来 Vec.produce \n -> (n+1) 是这种原因？每个数字对应一个『爸爸』树？

childFamily l r = case (l, r) of
(Pa x fx, Pa y fy) -> if fx == fy then True else (childFamily fx fy)
otherwise -> False

准确来说也不『新』了，冰封 2016 年 8 月就在博客上发了离散化求并查集的题解...（汗）

which 是我今天看瞎眼也不知道为什么的题目，早在 3 年前...
唉

啊！才发现其实 main 里只是分配初始化一个算法全局要用到的数据结构而已... 本身这个数据结构是边查询边更新的

我自己瞎 JB 写了一个发现也可以 pass 测试数据（时间限制应该也 OK），可是我还是没有那个直觉... 虽然我写了，但是只是默写而已

因为我躺床上也想了很久都没有结果（都是一些比较浅层的结论，似乎靠树形图 也没有特别多的效果）
思量着 要上 可视化 拿命分析 只要分析完能力能有提升，哪怕以后都要拿命分析 也在所不辞

#Haskell XJB 写的树状数组离散化并查集，不过是抄的...（默写的） 自己还不是很理解，看看

#Haskell #Algorithm 仅仅是比原版换了一点命名大概，主体逻辑没有区别，但即使是模板 弄不懂的话 也是没有意义的呢。

来看一下我们的测试题目。首先是初始化并查集内容（Zi=1）部分

O A B
1 1 2
1 3 4
1 2 3

现在这个集合里 应该怎么样呢？
是数组 离散化 存储的一个树，数组是一个 mapping，K 是 Int, V 是 Int

a=1; b=2, 先去找两个 deep ancestor: ap, bp
拿到的肯定是 vec[1] vec[2] 本身（n == i）
然后去存 nodes[1].parent = nodes[2] 就发现 1 和 2 是一锅的

3 4 同理，n[3].parent = n[4]; n[4].parent = nil(4)

2 3 的话，就体现 优化，要找爸爸树
2 的话，找到 n[2] （是 1 的爹），然后它是爹的 child
3 的话，找到 n[3] （是 4 的 娃），然后它的爹就是 4, 顺带传递性相等， n[3] 的爹 也是 4 肯定
n[3] = n[4]

这样的话，A={1,3,2} B={2,4,3}

首先就是构造这种 爹树

1 -> 2
2 -> 2 (inserting 2, 3)
2 -> nil
3 -> 4
3 -> 4 (inserting 2, 3)
4 -> nil

集合并的是那 (A | B) = {1,2,4}，那就发现其实 22 33 都没有意义，为什么不当自己的爹，剪掉
那并还有 B 没有的 为什么不直接用空间 保存住，可是不是分开保存的
必须是树，在一起的话 有一个爹 不是一集人不认一个爹，那爹是怎么一起认的呢？就是当儿子、合并

那如何查找爹树？

1 2 是否在同一集合内？
1 -> 2
2 -> 2 那都是一个爹的 娃，是

2 3 是否在一个集合呢？

2 -> 2 可是 3 是否有一个爹呢？
3 -> 4 -> 4 没有一个爹（找完了都

3 4 是否呢？
3 -> 4
4 -> 4
有一个爹，是一集和的 爹（

... 就是 merge 的时候 deep merge 找野爹（跑，是最远的爹）然后每层都去建立传递关系
find 的时候问野（爹 是否是一个爹（之前同集合的都传递了）
每个数 都可能是别人的爸爸（喜当爹，逃

有点 LuaOOP 虚表继承的感觉，每个树都可能有爹，爹有很多儿子、爹只能有一个爹

虚表是每次递归查找到了复制，并查树也是
两者都是传递性，不过一个是为了缓存（也是性质）传递、一个是一元相关性传递

cats 就是找某个 node 最远的爹，然后一下解决所有娃子的传递性问题，concat 到一起去
对应的 find 实现是为了践行这个理念，顺便有缓存剪枝

可是具体的，比如 find 的 (make me dptr) 到底是不是删掉也正确，不清楚...

我终于知道为什么很多出版物里都能找到不完美的地方了，原来尽可能去修改就有这么难啊...

本来已经修改了很多地方，换掉了不少有问题或者可以改进的表达，再看一遍，我又找到比原来还多数目的...

目前我依然在修改，将在基本完成后对内容进行最后的校验

今天明天内，我会给它加一些 JavaScript 小挂件来提升阅读体验

目前还在对内容进行校对

当然是不会存在什么断章取义的，我会给每个链接部分都加上预览的功能，方便没法科学上网的看

此外，我还会和谐掉一些内容，放在 <template nsfw> 里，再随便多加些点评

#acg 啊... 好可惜啊 #China