普通平衡树

第一次打Treap， 谁家好人一个模板一百多行啊）

怎么判断数存不存在， 如果不存在咋办）

其实速度还可以吧 除了1，2这两个点T了其他都30ms下

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int tr_size, root;
struct Treap {
	int left, right, val, cnt = 0, size = 0, fix;
} tr[N];

void update (int &p) {
	tr[p].size = tr[tr[p].left].size + tr[tr[p].right].size + tr[p].cnt;
}

void Zag (int &p) {
	int t = tr[p].right;
	tr[p].right = tr[t].left;
	tr[t].left = p;
	tr[t].size = tr[p].size;
	update (p);
	p = t;
}

void Zig (int &p) {
	int t = tr[p].left;
	tr[p].left = tr[t].right;
	tr[t].right = p;
	tr[t].size = tr[p].size;
	update (p);
	p = t;
}

void Insert (int &p, int val) {
	if (!p) {
		p = ++ tr_size;
		tr[p].val = val;
		tr[p].fix = rand();
		tr[p].cnt = tr[p].size = 1;
		tr[p].left = tr[p].right = 0;
		return ;
	}
	else tr[p].size ++;
	if (tr[p].val == val) {
		tr[p].cnt ++;
	} else if (tr[p].val > val) {
		Insert (tr[p].left, val);
		if (tr[tr[p].left].fix < tr[p].fix) Zig (p);
	} else {
		Insert (tr[p].right, val);
		if (tr[tr[p].right].fix < tr[p].fix) Zag (p);
	}
	return ;
}

void Delete (int &p, int val) {
	if (tr[p].val == val) {
		if (tr[p].cnt > 1) tr[p].cnt -- , tr[p].size --;
		else if (!tr[p].left || !tr[p].right) p = tr[p].left + tr[p].right;
		else if (tr[tr[p].left].fix < tr[tr[p].right].fix) Zig (p) , Delete (p, val);
		else Zag (p) , Delete (p, val);
		return ;
	}
	tr[p].size --;
	if (val < tr[p].val) Delete (tr[p].left, val);
	else Delete (tr[p].right , val);
	return ;
}

int Pre (int &val) {
	int x = root, res = 0;
	while (x) {
		if (tr[x].val < val) res = tr[x].val , x = tr[x].right;
		else x = tr[x].left;
	}
	return res;
}

int Las (int &val) {
	int x = root, res = 0;
	while (x) {
		if (tr[x].val > val) res = tr[x].val , x = tr[x].left;
		else x = tr[x].right;
	}
	return res;
}

int Kth (int &k) {
	int x = root;
	while (x) {
		if (tr[tr[x].left].size < k && k <= tr[tr[x].left].size + tr[x].cnt) return tr[x].val;
		if (tr[tr[x].left].size >= k) x = tr[x].left;
		else k -= (tr[tr[x].left].size + tr[x].cnt) , x = tr[x].right;
	}
	return 0;
}

int Rank (int &val) {
	int x = root , res = 0;
	while (x) {
		if (tr[x].val == val) return res + tr[tr[x].left].size + 1;
		if (tr[x].val > val) x = tr[x].left;
		else res += (tr[tr[x].left].size + tr[x].cnt) , x = tr[x].right;
	}
}

inline int read () {
	char c = getchar ();
	int x = 0, f = 1;
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar (); }
	while (c >= '0' && c <= '9') { x = x * 10 + (c - 48); c = getchar(); }
	return x * f;
}

int n, mode, x;
int main() {
	n = read ();
	for (int i = 1; i <= n; i ++) {
		mode = read() , x = read();
		switch (mode) {
			case 1 : Insert (root, x); break;
			case 2 : Delete (root, x); break;
			case 3 : printf ("%d\n", Rank (x)); break;
			case 4 : printf ("%d\n", Kth (x)); break;
			case 5 : printf ("%d\n", Pre (x)); break;
			case 6 : printf ("%d\n", Las (x)); break;
			default : break;
		}
	}
	return 0;
}

我这辈子最讨厌的就是平衡树和线段树