1. 题目

BZOJ传送门= ̄ω ̄=
LUOGU传送门= ̄ω ̄=
CODEVS传送门= ̄ω ̄=

2. 题解

真是气死人啦!
调了一晚上+一个课间操,都没找出bug。
重写了3次treap,第一次用指针,第二次用vector,第三次用静态数组。。。
都错的一模一样!
为什么呢?
中午绝望的我无意中看了看代码中不是treap的地方。。。
merge函数中这句话:

。。。
你大爷啊!我居然挂在了这里!。。。应该这样写:

。。。。。。。。。。。。。。。。
想起昨天考试,>=写成了>,从100分掉到了10分。。。。
一种来到非洲的感觉油然而生!
好吧,其实这题很水,就是个并查集维护集合关系,然后启发式合并。
思路具体去看我以前写的用pb_ds解决的那个博客吧:
http://k-xzy.cf/?p=786

treap代码:
指针treap用了个小技巧,本来节点的构造函数会把节点的l和r指到NULL上。我把它指到了一个叫def(default)的节点上,这样可以不用每次都判断是否为NULL防止段错误了。
代码1(指针treap):

静态数组大小开$nlogn$的大小(稍微开大一点)就行了,因为启发式合并复杂度为$nlogn$
代码2(静态数组treap):