toxic treap

mt19937 mt;
constexpr int maxn=1e5;
static int k[maxn],v[maxn],l[maxn],r[maxn],top=0;

inline node(int x){
    k[top]=x,v[top]=mt();
    l[top]=r[top]=-1;
    return top++;
}

int merge(int a,int b){
    int rt=-1,*cur=&rt;
    while(~a&&~b){
        if(v[a]<v[b])
            *cur=a,cur=&r[a],a=r[a];
        else
            *cur=b,cur=&l[b],b=l[b];
    }
    *cur=~a?a:b;
    return rt;
}

void split(int t,int x,int *a,int *b){
    while(~t){
        if(k[t]<x)
            t=r[*a=t],a=&r[*a];
        else
            t=l[*b=t],b=&l[*b];
    }
    *a=*b=-1;
}

void insert(int& t,int x){
    int l,r;
    split(t,x,&l,&r);
    t=merge(merge(l,node(x)),r);
}

void print(int t){
    if(!~t) return;
    print(l[t]);
    cout<<k[t]<<' ';
    print(r[t]);
}

inline void solve() {
    int tree=-1;
    for(auto i:{1,5,4,2,0,3,6,9,7,8})
        insert(tree,i);
    print(tree);
}