Treap

treap.cpp

struct Treap{
	typedef struct _Node {
		int x,y,c;
		_Node *l, *r;
		_Node(int _x): x(_x), y(rand()), c(1), l(NULL), r(NULL) {}
		~_Node() { delete l; delete r; }
		void recalc() { c = 1 + (l?l->c:0) + (r?r->c:0); }
	} *Node;

	int count(Node v) { return v?v->c:0; }	

	Node root;
	Treap(): root(0) { srand(time(NULL)); }
	~Treap() { delete root; }

	Node merge(Node l, Node r) {
		if(!l | !r) return l?l:r;
		if(l->y > r->y) {
			l->r = merge(l->r,r);
			l->recalc();
			return l;
		} else {
			r->l = merge(l,r->l);
			r->recalc();
			return r;
		}
	}

	void split(Node v, int x, Node &l, Node &r) {
		l = r = NULL;
		if(!v)
			return;
		if(v->x < x) {
			split(v->r, x, v->r, r);
			l = v;
		} else {
			split(v->l, x, l, v->l);
			r = v;
		}

		v->recalc();
	}

	Node search(Node v, int x) {
		if(!v || v->x == x) return v;
		else if(x < v->x) return search(v->l,x);
		else return search(v->r,x);
	}

	Node search(int x) { return search(root,x); }

	void insert(int x) {
		if (search(x)) return;

		Node l,r;
		split(root,x,l,r);
		root = merge(merge(l,new _Node(x)),r);
	}

	void erase(int x) {
		if (!search(x)) return;

		Node l,m,r;
		split(root,x,l,m);
		split(m,x+1,m,r);
		delete m;
		root = merge(l,r);
	}

	int kth(Node v, int k) {
		int num_l = count(v->l);
		if(k <= num_l)
			return kth(v->l, k);
		else if(k > num_l + 1)
			return kth(v->r, k-num_l-1);
		else
			return v->x;
	}

	int kth(int k) { return kth(root, k); }

	int lt(Node v, int x) {
		if(!v)
			return 0;

		if(x == v->x)
			return count(v->l);
		else if(x < v->x)
			return lt(v->l, x);
		else
			return count(v->l)+1+lt(v->r, x);
	}

	int lt(int x) { return lt(root, x); }

	size_t size() { return count(root); }
};