关于启发式合并的笔记
扯淡
看完了《国家集训队2015论文集》里面启发式合并的“对数据结构合并”这一部分（后面的由于本蒟比较弱看不懂），然后找了一两个题目。
同样，在接下来的叙述中，可能数据范围不太准。大致明白就好。
思想
都写过并查集的按秩合并。按秩合并可以把并查集的暴力严格压缩到O(nlogn)（源自UOJ某大佬）。原理在于：我们按秩合并的时候，把size小的连通块加入到size大的连通块里面。size小的路径增加了1，大小翻倍。
自然我们只能够增加logn次，于是总的时间复杂度为O(nlogn)。
类似的，还有很多东西可以 启发式合并。
比方说堆。虽然都是用的左偏树，但是作为不会左偏树的蒟蒻，学一学启发式合并也是可以的。我们遍历size小的堆中的元素，插入到size大的堆中。一次合并size小的被遍历了一次，大小翻倍。
自然每个点只会被遍历logn次，于是总的时间复杂度为O(nlog^2n)。
再者如Splay。我们遍历size小的Splay中的元素，插入到size大的Splay中。一次合并size小的被遍历了一次，大小翻倍。
自然每个点只会被遍历logn次，于是总的时间复杂度为O(nlog^2n)。
诸如此类……
不过我们发现，我们在合并的时候，要保证复杂度只在size小的部分增加。如果合并一次，在size大的部分与size小的u、部分均增加，那么复杂度就相当于暴力了。
我们在合并的时候，常常需要遍历size（当前需要合并的部分的大小）小的部分——
void ergodic(int x){
}
在我们遍历的时候，一般先处理完所有的子部分，再对这个点进行处理。
比方说遍历一棵Splay，我们先把儿子全部处理，再处理当前节点。
BZOJ 3123
题目大意：
给出一片大小为n的森林，点有点权，给出m个操作：
查询路径第k小。
连一条边。
n,m<=1e5
个人解法：
自然我们不好用LCT维护。考虑到如果没有连边操作，我们直接建一棵树上主席树即可。
现在有连边操作，但是发现我们我们只需要知道lca、Fa与树上前缀主席树即可。我们考虑较方便维护的倍增数组。
每一次合并，我们选择size较小的树进行遍历，重新更新它的倍增数组与主席树的节点。
注意这里需要更新前缀主席树，由此需要先更新当前节点，再处理子树。
那么这样的时间复杂度为O(nlog^2n)，空间复杂度为O(nlog^2n)。
BZOJ 2733
题目大意：
给出一张n个点，m条边的无向图，给出q个操作：
查询连通块内第k小
连一条边
n,m,q<=1e5
个人解法：
和上一个SDOI的题好像啊。但是它不是树。于是我们用一个有序的容器就好了。比方说一棵Splay。
同样Splay也支持启发式合并。Splay可以实现查询第k小，维护Splay中的子树大小即可。
不过为了避免重复合并，我们可以用一个并查集维护连通性，并查集路径压缩就可以了，时间复杂度远不及启发式合并的。
这样的时间复杂度是O(nlog^2n)的。
一个关于Splay空间压缩的方法
我们发现在上题中，Splay的不会增加点，只是一个节点从这一棵Splay转移到了另一棵Splay。这样我们不用重新开节点，可以直接转化一下父亲儿子的指针，就可以避免至少O(nlogn)的空间花费。
在插入的时候，代入两个参数p与v，表示把v这个节点插入到p为根的Splay中。
在ergodic（遍历size小的部分的过程）中，先遍历左儿子与右儿子，之后把当前节点所有在原来Splay中的关系与维护的子树关系全部清空，只保留到最初始的状态。
之后我们插入即可。
在遍历的时候可能需要维护一个根ro，因为在插入的时候，为了维护Splay复杂度需要旋转到根，于是根会变化。
大致代码如下：
https://code.csdn.net/snippets/2211589
BZOJ 2809
题目大意：
给出一棵大小为n的树，点有点权与代价。给出一个M，选择一个节点x作为子树的根，在子树中选择若干个点，使得点的代价之和不超过M，且x的点权乘上选择的点数最大。
n<=1e5
个人解法：
自然我们不难想到贪心。枚举子树的根，用一个堆维护子树里面前k个最小的节点，保证这些节点不会带价值和不会超过M。
DFS的时候，先处理完所有的子树，然后把所有子树对应的堆合并起来。更新答案。
不过由于本蒟比较菜不会写左偏树不会写链式储存的堆，于是用了一棵Splay来处理这一玩意。
BZOJ 1483
题目大意：
给出一个长度为n的序列，每个格子上有一种颜色。现在给出m个操作：
把所有x的颜色变为y的颜色
查询整个序列的颜色段的数量
n,m<=1e5
个人解法：
我们发现每一次变色都是可能会出现颜色段的合并，但是不会出现颜色段的分裂。这样一来我们就可以尝试对每个颜色都用一个数据结构来维护出现的颜色段。
在合并的时候就直接把size小的合并进入size大的即可。
看到很多博客都是用链表做的。然而我对链表不熟悉。于是没有用他们的做法。用了Splay。
细节问题：
涉及到一些换根与前驱后继的合并。需要仔细思考如何维护根，以及保留哪一些节点。
还有对于没有合并而是直接一种颜色变化到另一种不存在的颜色，以及不存在的颜色变化为一种颜色的处理都需要注意。
说起来简单写起来还是有些恼火的。
BZOJ 3545
题目大意：
给出一张n个点m条边的无向图，边有边权，点有点权，给出q个询问：询问某个点u在允许通过边权不超过x的情况下，可以走到的点的第k小的点权。
n,m,q<=1e5
个人解法：
自然想到离线再排序。
之后边处理询问，边加入边，变为了合并。我们用一棵Splay即可维护连通块内的点的信息即可。
好像和前面那一道HNOI差不蛮多的样子。
建议用Treap。Splay作为容器来使用自然是没有Treap等诸多平衡树快的。
小结
于是打了一天的Splay。Splay还是比较强大似乎啥都可以套上虽然常数有点大。
没有像前几天写并查集那样偶尔还可以排名到BZOJ第一页……
不过就论启发式合并数据结构而言，似乎还是比较好理解的。代码也不长。处理合并问题还挺方便的。
比方说某LCT想做的事情，换根+子树查询+连边=分类讨论+树链剖分+启发式合并。不知道对不对……？
1e5的数据，用O(nlog^2n)的还是比较轻松的。不过如果有5e5，似乎需要卡常（最讨厌tm的卡常了）？1e6大概只可以带一个log了吧。自然就不能使用启发式合并了。