treap

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct node{
    int lc,rc;//左右 
    int sum;//重复数 
    int id;//当前节点编号
    int size;//当前节点总个数 
    int rnd;// 优先级 
}tree[maxn];
int cnt;
void update(int &k){//更新节点k的size 
    int &lc=tree[k].lc;
    int &rc=tree[k].rc;
    tree[k].size=tree[lc].size+tree[rc].size+tree[k].sum;
}
void left_rotate(int &k){//左旋 
    int t=tree[k].rc;
    tree[k].rc=tree[t].lc;
    tree[t].lc=k;
    tree[t].size=tree[k].size;
    update(k);
    k=t;
} 
void right_rotate(int &k){//右旋 
    int t=tree[k].lc;
    tree[k].lc=tree[t].rc;
    tree[t].rc=k;
    tree[t].size=tree[k].size;
    update(k);
    k=t;
} 
void insert(int &k,int x){//k位置插x 
    if(k==0){
     k=++cnt;
     tree[k].id=x;
     tree[k].size=1;
     tree[k].sum++;
     tree[k].rnd=rand();
     return ;   
    }
    tree[k].size++;
    int &lc=tree[k].lc;
    int &rc=tree[k].rc;
    if(x<tree[k].id){
        insert(lc,x);
        if(tree[lc].rnd<tree[k].rnd)
        right_rotate(k);
    }
    if(x>tree[k].id){
        insert(lc,x);
        if(tree[rc].rnd<tree[k].rnd)
        left_rotate(k);
    }
    if(x==tree[k].id)tree[k].sum++;
}
void del(int &k,int x){
    if(k==0){
        return ;
    }
    int &l=tree[k].lc;
    int &r=tree[k].rc;
    if(x==tree[k].id){
        if(tree[k].sum>1){
            tree[k].sum--;
            tree[k].size--;
        }
        if(l*r==0)
        k=l+r;
        else {
            if(tree[l].rnd<tree[r].rnd)
            right_rotate(k);
            else left_rotate(k);
            del(k,x);
        }
    }
    else{
        tree[k].size--;
        if(x>tree[k].id)del(r,x);
        else 
        del(l,x);
    } 
    return ;
}
int main(){
    srand(time(0)); 
    
    
    return 0;
} 

treap

原文：https://www.cnblogs.com/hjh179/p/10726264.html