Treap

// Treap
// Tested: bjtu1057, hdu1004, pku1002
typedef int KEY;
typedef int VALUE;
struct node_t {
	int ch[2], pr;
	KEY key;
	VALUE value;
} T[maxn];
int size; // init: size = 0
int new_node() {
	T[size].ch[0] = T[size].ch[1] = -1, T[size].pr = rand();
	return size++;
}
struct treap_t {
	int root; // init: root = -1
	void clear() {
		root = -1;
	}
	void adjust(int &p, int k) {
		int x = T[p].ch[k];
		T[p].ch[k] = T[x].ch[1 - k], T[x].ch[1 - k] = p, p = x;
	}
	void insert(int &p, const KEY &key, const VALUE &value) {
		if (p == -1) {
			p = new_node(), T[p].key = key, T[p].value = value;
		} else if (key == T[p].key) {
			T[p].value += value;
		} else {
			int k = key < T[p].key ? 0 : 1;
			insert(T[p].ch[k], key, value), adjust(p, k);
		}
	}
	void erase(int &p, const KEY &key) {
		if (p == -1) return;
		if (key == T[p].key) {
			int L = T[p].ch[0], R = T[p].ch[1], k = L != -1 ? 0 : -1;
			if (R != -1 && (k == -1 || T[R].pr < T[L].pr)) k = 1;
			if (k == -1) p = -1;
			else adjust(p, k), T[p].ch[1 - k] = -1;
		} else {
			int k = key < T[p].key ? 0 : 1;
			erase(T[p].ch[k], key);
		}
	}
	int find(int p, const KEY &key) {
		if (p == -1 || key == T[p].key) return p;
		int k = key < T[p].key ? 0 : 1;
		return find(T[p].ch[k], key);
	}
	int lower_bound(int p, const KEY &key) {
		if (p == -1 || key == T[p].key) return p;
		int k = key < T[p].key ? 0 : 1;
		if (T[p].ch[k] == -1) return k == 1 ? -1 : p;
		return lower_bound(T[p].ch[k], key);
	}
	int upper_bound(int p, const KEY &key) {
		int x = lower_bound(p, key);
		if (x == -1 || key < T[x].key) return x;
		return T[x].ch[1];
	}
} treap;