最近学习了treap，找了道题目做做 全抄hz...

因为普通的二叉树，会退化成链；

所以你把读入打乱顺序再构造二叉树，就明显卡不掉；

平平均深度logn；

treap就是这样的；

在插入一个数时，我们搞一个rnd，赋值随机；

然后如果当前的这个节点rnd小于其父节点，那么就把他转到父节点的位置；

这样好比是给这个节点一个随机的顺序；

那么即使毒瘤出题人把一开始数据的顺序搞特殊，故意要卡你，因为每个数据有了这么一个随机位置，相当于把读入打乱啦，所以卡不掉；

要是被卡了是RP问题；

百度百科；

我们浅谈关于转；

这里我们要把3节点转到上面来；

我们发现转好之后几个数字的再二叉树里的大小关习是不变的；

这就是我们转的原理；

可以看出2-1|||||||||3-5这两条边是不变的；

自己感受感受；

其实转就是怎么个过程，换了种方式存储信息；

但转就把3节点向上移动了；

---

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct treap{    int l,r,v,size,w,rnd;//size是包括根节点，这个子树的节点总数，w是这个v值出现了几次，所以treap里面每个值只有一个； }tr[100005];int m,x,y,z,root,size;//root是根节点，根节点不一定是1，因为会转掉的；size就个计数 void now(int k){
    tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;}//更新size void lturn(int &k){
    //这个过程建议大家直接好好模拟，思考；     int t=tr[k].r;    tr[k].r=tr[t].l;    tr[t].l=k;    tr[t].size=tr[k].size;    now(k);    k=t;}void rturn(int &k){    int t=tr[k].l;    tr[k].l=tr[t].r;    tr[t].r=k;    tr[t].size=tr[k].size;    now(k);    k=t;}void insert(int &k,int x){    if(!k){        k=++size;        tr[k].size=tr[k].w=1;        tr[k].v=x;        tr[k].rnd=rand();//我们只需要一组随机数，所以不用种子；         return;    }    tr[k].size++;    if(tr[k].v==x){
    tr[k].w++;return;}//如果已经出现过直接加再w上     if(tr[k].v
          
           1){ tr[k].size--;tr[k].w--;return;}//如果有多个那删一个 if(tr[k].l*tr[k].r==0){k=tr[k].l+tr[k].r;return;}//这个是有一个节点和无节点的情况 int l=tr[k].l,r=tr[k].r; if(tr[l].rnd
           
            x)return Rank(tr[k].l,x); return tr[tr[k].l].size+tr[k].w+Rank(tr[k].r,x);}int num(int k,int x){ if(!k)return 0; if(x<=tr[tr[k].l].size)return num(tr[k].l,x); if(x>tr[tr[k].l].size+tr[k].w)return num(tr[k].r,x-tr[tr[k].l].size-tr[k].w); return tr[k].v;}int pro(int k,int x){ //推荐大家用hzwer的写法，这个写法比较乱 if(!k)return 0; if(tr[k].v>=x)return pro(tr[k].l,x); int ans=pro(tr[k].r,x); if(ans)return ans;else return tr[k].v;}int sub(int k,int x){ if(!k)return 0; if(tr[k].v<=x)return sub(tr[k].r,x); int ans=sub(tr[k].l,x); if(ans)return ans;else return tr[k].v;}int main(){ scanf("%d",&m); while(m--){ scanf("%d%d",&y,&x); if(y==1)insert(root,x);else if(y==2)del(root,x);else if(y==3)printf("%d\n",Rank(root,x));else if(y==4)printf("%d\n",num(root,x));else if(y==5)printf("%d\n",pro(root,x));else if(y==6)printf("%d\n",sub(root,x)); }}