代码

#include <bits/stdc++.h>
using namespace std;

namespace AVL {
	struct node_t {
		int val, siz, height;
		node_t *ch[2];

		void pushup() {
			siz = ch[0]->siz + ch[1]->siz + 1;
			height = max(ch[0]->height, ch[1]->height) + 1;
		}
		int factor(int d) const {
			return ch[d]->height - ch[d ^ 1]->height;
		}

		int get_val() const {
			return val;
		}
		
		void modify(int w) {
			val = w;
		}

		node_t(char _pad1 = 0, char _pad2 = 0) : val(0), siz(0), height(0) {
			ch[0] = ch[1] = this;
		}
		node_t(int);
	}*null(new node_t(0, 0)), *root(null);

	node_t::node_t(int _val) : val(_val), siz(1), height(1) {
		ch[0] = ch[1] = null;
	}

	void rotate(node_t* &o, int d) {
		node_t* t = o->ch[d ^ 1];
		o->ch[d ^ 1] = t->ch[d];
		t->ch[d] = o;
		o->pushup(), t->pushup();
		o = t;
	}

	void balance(node_t* &o, int d) {
		if (o->ch[d]->factor(d ^ 1) > 0)
			rotate(o->ch[d], d);
		rotate(o, d ^ 1);
	}

	void insert(node_t* &o, int w) {
		if (o == null) {
			o = new node_t(w);
			return;
		}
		int d = w < o->get_val() ? 0 : 1;
		insert(o->ch[d], w);
		o->pushup();
		if (o->factor(d) == 2) {
			balance(o, d);
		}
	}

	void erase(node_t* &o, int w) {
		if (o == null)
			return;
		int d;
		if (o->get_val() == w) {
			if (o->ch[0] == null || o->ch[1] == null) {
				o = (o->ch[0] == null) ? o->ch[1] : o->ch[0];
				return;
			} else {
				node_t *t = o->ch[0];
				while (t->ch[1] != null) {
					t = t->ch[1];
				}
				o->modify(t->get_val());
				d = 0;
				erase(o->ch[0], t->get_val());
			}
		} else {
			d = w < o->get_val() ? 0 : 1;
			erase(o->ch[d], w);
		}
		o->pushup();
		if (o->factor(d ^ 1) == 2) {
			balance(o, d ^ 1);
		}
	}

	int find_by_order(node_t* o, int k) {
		if (k == o->ch[0]->siz + 1)
			return o->val;
		if (k <= o->ch[0]->siz)
			return find_by_order(o->ch[0], k);
		return find_by_order(o->ch[1], k - o->ch[0]->siz - 1);
	}

	int order_of_key(node_t* o, int w) {
		if (o == null)
			return 1;
		if (w <= o->val)
			return order_of_key(o->ch[0], w);
		else
			return order_of_key(o->ch[1], w) + o->ch[0]->siz + 1;
	}

	int precursor(node_t* o, int w) {
		if (o == null)
			return -INT_MAX;
		if (w <= o->val)
			return precursor(o->ch[0], w);
		else
			return max(o->val, precursor(o->ch[1], w));
	}

	int successor(node_t* o, int w) {
		if (o == null)
			return INT_MAX;
		if (w >= o->val)
			return successor(o->ch[1], w);
		else
			return min(o->val, successor(o->ch[0], w));
	}
}

using namespace AVL;

int N;

int main() {
	N = 1000000;
	for (int opt, x, i = 1; i <= N; i++) {
		opt = rand() % 6 + 1;
		x = rand() * rand();
		switch (opt) {
			case 1:
				insert(root, x);
				break;
			case 2:
				erase(root, x);
				break;
			case 3:
				printf("%d\n", order_of_key(root, x));
				break;
			case 4:
				printf("%d\n", find_by_order(root, x));
				break;
			case 5:
				printf("%d\n", precursor(root, x));
				break;
			case 6:
				printf("%d\n", successor(root, x));
				break;
        }
	}

	return 0;
}

评测结果