旋转treap：

key为给定值 满足二叉树性质

weight为随机值 满足堆性质

没有双旋 只有单旋

而且要分别写左旋和右旋

insert之后一定要旋转 不然会不满足Treap性质

区间翻转之类的好像做不到 对于区间类问题似乎都比较弱(。・・)ノ

那么我为什么还要去看这玩意儿呢

不仅是因为非旋Treap可持久化的问题

还因为在写树套树的时候

我发现写splay是经常需要查前驱后继的对不对

包括删除/直接查询

按照我们平常的习惯 为了避免re我们还需要在每一棵树插一个inf和一个-inf

然而的树套树的时候我觉得这么插入实在是有点无趣了

刚好又早仰能可持久化的非旋treap大名

就刚好在2017的last day学一下好了

感觉好厉害 而且还资瓷处理区间啊

然后我一开始看到merge需要A树所有节点的key小于b树最小节点才能操作的时候是懵逼的

而且当我看到不满足这个条件就会需要启发式合并是更懵逼的

结果

我思考了一会儿

突然发现 好像经常性的操作是split之后再merge的

然后我们split操作是按key值把树剖开的 所以经常性的是能满足上面情况的

在满足这一情况之后我们就可以类似于左偏树一样的递归合并啦（比较的是weight值）

这玩意儿

真的

太好写了吧！

而且

好有逻辑！

我爱它！！！！