左偏树

具体见OI-wiki，但是OI-wiki对左偏树的“外节点”的定义好像错了，其实应该就是指空节点；删除任意一个数的那个部分就不用看了，没啥用

设\(f(k)\)表示\(\text{dist}\)为\(k\)的左偏树最少包含的点，则有\(f(k)≥2^k-1\)

证明：\(f(k)\)单调递增，这是因为此时右子树的\(\text{dist}\)肯定为\(k-1\)，也就包含\(f(k-1)\)个点，算上根节点和左子树，于是有\(f(k)\)单增

显然\(f(1)≥2^1-1=1\)

假设当\(n=k-1\)时，\(f(n)≥2^n-1\)；当\(n=k\)时，\(f(n)≥2^{k-1}-1+2^{k-1}-1+1=2^k-1\)（右子树为\(f(k-1)\)个节点，左子树至少为\(f(k-1)\)个节点，算上根节点），证毕

也就是说至少有\(\text{dist-1}\)层是满二叉树，于是时间复杂度得以保证

那么对于这道题目，我们还需要用并查集去维护左偏树。具体来说，每个左偏树都对应一个并查集，而且左偏树的根节点就是并查集的代表元素。于是前面三个操作都很容易解决了，但是第四个操作看起来要对并查集进行分离。实际上不用，这里解锁一个新操作，即并查集的换根操作。删除左偏树的根节点后，我们在并查集中不删除代表元素；合并左儿子和右儿子之后，新的左偏树的根作为并查集的代表元素，此时只需要将原来的根节点的父亲指向新的根节点，新的根节点的父亲指向自己就好了。易知这样做不会影响答案

具体见打卡代码