1. 题目

传送门= ̄ω ̄=

2. 题解

这题调了我好久好久啊!
其实就一模板题,用来学Treap。。。
一开始写的指针树,都不知道飞到哪里去了
后来写了个数组的但是超级辣鸡,数组都能段错误。。。
然后照着hzwer的代码改了一下,还是有错误。
最后无语了,自己重写了一份。
然而还是WA了一次。
仔细一看发现是求kth的时候把一个变量写错了。。。

真畸形
建议treap用静态数组写,虽然会浪费一些空间,但是理论上会快一些,而且可以设置节点0为不存在的节点,这样就不用每次判断一下是否存在这个节点防止段错误了。
如果你实在不想浪费空间就搞个空间回收栈即可。

代码: