treap_(law_que_entendeu).cpp

#include <bits/stdc++.h>

using namespace std;

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

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

inline 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);
	else return find(t->r, v);
}

void merge(node*& t, node *a, node *b){
	if(a == nullptr){
		t = b;
		return;
	}else 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 print(node *t){
	if(!t) return;
	print(t->l);
	cout << t->v << " ";
	print(t->r);
}

inline void insert(node*& t, int v){
	if(find(t, v)) return;
	node *a=nullptr, *b=nullptr, *aux = new node(v);
	split(t, a, b, v);
	merge(a, a, aux);
	merge(t, a, b);
}

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

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	node *t = nullptr;
	insert(t, 2);
	insert(t, 3);
	insert(t, 1);
	insert(t, 4);
	insert(t, 5);
	print(t);
	cout << "\n";
	erase(t, 4);
	insert(t, 121311);
	print(t);
	
	cout << "\n";
	return 0;
}