treap_law.cpp

#include <bits/stdc++.h>

using namespace std;

struct node{
	int v, w;
	node *l, *r;

	node(int v_=0){
		v = v_;
		w = rand();
		l = nullptr;
		r = nullptr;
	}
};

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

void merge(node*& t, node *a, node *b){
	if(a == nullptr){
		t = b;
		return;
	}
	if(b == nullptr){
		t = a;
		return;
	}

	if(a->w >= b->w){
		merge(a->r, a->r, b);
		t = a;
	}else{
		merge(b->l, a, b->l);
		t = b;
	}
}

void split(node *t, node*& a, node*& b, int k){
	if(t == nullptr){
		a = b = nullptr;
		return;
	}

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

void insert(node*& t, int v){
	if(find(t, v)) return;

	node *a=0, *b=0;
	node *it = new node(v);
	split(t, a, b, v);
	merge(a, a, it);
	merge(t, a, b);
}

void erase(node*& t, int v){
	if(!find(t, v)) return;
	node *a=0, *b=0, *aux=0;
	split(t, a, b, v);
	split(b, aux, b, v+1);
	merge(t, a, b);
	delete aux;
}

void print(node *t){
	if(!t) return;
	print(t->l);
	cout << t->v << " ";
	print(t->r);
}

int main(){
	node *law=nullptr;
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		insert(law, x);
	}
	print(law);
	return 0;
}