treap.cpp

#include <bits/stdc++.h>

using namespace std;
struct node{
    int v, w;
    node *l, *r;
    node(){
        l = NULL;
        r = NULL;
        v = 0;
        w = rand();
    }
};
typedef node*& node_t;

bool find(node* t, int v){
    if(t == NULL) return false;
    
    if(t->v == v) return true;
    else if(v < t->v) return find(t->l, v);
    else return find(t->r, v);
}

void merge(node_t t, node* l, node* r){
    if(l==NULL){
        t = r;
        return;
    }
    if(r==NULL){
        t = l;
        return;
    }
    if(l->w >= r->w){
        merge(l->r, l->r, r);
        t = l;
    }else{
        merge(r->l, l, r->l);
        t = r;
    }
}

void split(node* t, node_t l, node_t r, int v){
    if(!t) return void(l=r=0);

    if(t->v < v){
        split(t->r, t->r, r, v);
        l = t;
    }else{
        split(t->l, l, t->l, v);
        r = t;
    }
}

void insert(node_t no, int v){
    if(find(no, v)) return;
    node *l=NULL, *r=NULL;
    node *aux = new node;
    aux->v = v;

    split(no, l, r, v);
    merge(l, l, aux);
    merge(no, l, r);
}

ostream& operator<<(ostream& out, node* t){
    if(!t) return out;
    out << t->l << t->v << " " << t->r;
    return out;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    node *t = NULL;
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        insert(t, x);
    }
    cout << t << "\n";
    return 0;
}