rt, link

源码：

#include <iostream>
#include <vector>

#define which(x) (tree[tree[x].father].son[0] == x)

using namespace std ;

typedef int lint ;

struct SplayTree {
	
	struct Tree {
		lint cnt ;
		lint val ;
		lint lazy ;
		lint Size ;
		lint son[2] ;
		lint father ;
		
		inline void init(lint _v, lint _fa) {
			cnt = Size = 1 ;
			val = _v ;
			father = _fa ;
			son[0] = son[1] = 0 ;
			lazy = false ;
		}
	} ;
	
	vector<Tree> tree ;
	lint cnt_tree, now, root ;
	
	// 初始化树
	void init() {
		tree.resize(lint(1e5 + 5), Tree()) ;
		cnt_tree = 0 ; // 初始化 cnt
		root = 0 ; // 初始化根节点为0
	}
	
	// 更新：从当前点 x 向上更新父节点的子树大小
	void push_up(lint x) {
		if (x == 0) return ; // 防止访问空节点
		tree[x].Size = tree[x].cnt ;
		if (tree[x].son[0]) tree[x].Size += tree[tree[x].son[0]].Size ;
		if (tree[x].son[1]) tree[x].Size += tree[tree[x].son[1]].Size ;
	}
	
	// 旋转（单旋）将 x 点旋转到父结点处
	void revolve(lint x) {
		lint fa = tree[x].father ; // 父节点
		lint gf = tree[fa].father ; // 爷节点
		bool whichfa = which(x) ; // 此节点是父节点的 左/右 儿子
		bool whichgf = which(fa) ; // 父节点是爷节点的 左/右 儿子
		if (tree[x].son[!whichfa]) tree[tree[x].son[!whichfa]].father = fa ; // 子节点过继（1）
		tree[fa].son[whichfa] = tree[x].son[!whichfa] ; // 子节点过继（2）
		tree[x].son[!whichfa] = fa ; // 旋转到父节点之上（1）改变父子关系
		tree[gf].son[whichgf] = x ; // 旋转到父节点之上（2）改变父子关系
		tree[fa].father = x ; // 旋转到父节点之上（3）改变爷孙关系
		tree[x].father = gf ; // 旋转到父节点之上（4）改变爷孙关系
		push_up(fa), push_up(x) ; // 旋转到父节点之上（5）子树大小更新
	}
	
	// 旋转（双旋）：将 x 点旋转到目标点 y 的下方
	void Splay(lint x, lint y) {
		lint fa, gf ;
		if (x == y) return ;
		while (tree[x].father != y) {
			fa = tree[x].father ;
			gf = tree[fa].father ;
			if (gf != y) {
				if (which(fa) == which(x)) // x, fa, gf 三点共线
					revolve(fa) ; // 先旋转父节点
				else // x, fa, gf 三点呈之字形
					revolve(x) ; // 多旋转一次 x 节点
			}
			revolve(x) ;
		}
		if (!y)
			root = x ;
	}
	
	// 插入：在平衡树中以val 为权值插入一个节点
	void insert(lint val) {
		lint fa = 0 ;
		lint u = root ;
		while (u && tree[u].val != val) {
			fa = u ;
			if (val > tree[u].val) // 去右子树
				u = tree[u].son[1] ;
			else u = tree[u].son[0] ; // 去左子树
		}
		if (u) 
			tree[u].cnt ++ ;
		else {
			cnt_tree ++ ;
			u = cnt_tree ;
			if (fa) {
				if (val > tree[fa].val) // 去右子树
					tree[fa].son[1] = u ;
				else tree[fa].son[0] = u ; // 去左子树
			}
		}
		Splay (u, 0) ;
	}
	
	// 查找（1）：查找到数 x 并将它上提到根
	void Find(lint x) {
		lint u = root ;
		if (!u) return ;
		if (x > tree[u].val) 
			while (tree[u].son[1] && x != tree[u].val)
				u = tree[u].son[1] ;
		if (x < tree[u].val) 
			while (tree[u].son[0] && x != tree[u].val)
				u = tree[u].son[0] ;
		Splay(u, 0) ;
		return ;
	}
	
	// 查找（2）：查找一个给定值 x 的排名
	lint Rank(lint val) {
		Find(val) ;
		return tree[tree[root].son[0]].Size ;
	}
	
	// 查找（3）：查找第 x 小的元素
	lint Search(lint x) {
		lint u = root ;
		if (tree[u].Size < x)
			return -1 ;
		while (true) {
			if (x > tree[tree[u].son[0]].Size + tree[u].cnt){
				x -= tree[tree[u].son[0]].Size + tree[u].cnt ;
				u = tree[u].son[1] ;
			} else {
				if (tree[tree[u].son[0]].Size >= x)
					u = tree[u].son[0] ;
				else return tree[u].val ;
			}
		}
	}
	
	// 查找（4）：查找给定数 x 的前驱
	lint Predecessor(lint x) {
		Find(x) ;
		lint u = root ;
		if (tree[u].val >= x)
			return u ;
		u = tree[u].son[0] ;
		while (tree[u].son[1])
			u = tree[u].son[1] ;
		return u ;
	}
	
	// 查找（5）：查找给定数 x 的后继
	lint Successor(lint x) {
		Find(x) ;
		lint u = root ;
		if (tree[u].val >= x)
			return u ;
		u = tree[u].son[1] ;
		while (tree[u].son[0])
			u = tree[u].son[0] ;
		return u ;
	}
	
	// 删除：删除一个值为 x 的节点
	void Delete(lint x) {
		lint l = Successor(x) ;
		lint r = Predecessor(x) ;
		Splay(r, 0), Splay(l, r) ;
		if (tree[tree[r].son[0]].cnt > 1) {
			tree[tree[r].son[0]].cnt -- ;
			Splay(tree[r].son[0], 0) ;
		} else tree[r].son[0] = 0 ;
	}
} ;

lint n ;
lint opt, x ;

SplayTree splaytree ;

inline void read(lint &x) {
	char c ; bool b = true ;
	for (c = getchar() ; !isdigit(c) ; c = getchar())
		if (c == '-') b = !b ;
	for (x = 0 ; isdigit(c) ; c = getchar())
		x = x * 10 + c - '0' ;
	if (b == false)
		x *= -1 ;
	return ;
}

signed main() {
	read(n) ;
	splaytree.init() ; // 初始化树
	for (lint i = 1 ; i <= n ; i ++) {
		read(opt), read(x) ;
		if (opt == 1) splaytree.insert(x) ;
		else if (opt == 2) splaytree.Delete(x) ;
		else if (opt == 3) cout << splaytree.Rank(x) << '\n' ;
		else if (opt == 4) cout << splaytree.Search(x) << '\n' ;
		else if (opt == 5) cout << splaytree.Predecessor(x) << '\n' ;
		else if (opt == 6) cout << splaytree.Successor(x) << '\n' ;
	}
	return 0 ;
}

@Statax @DX3906_ourstar @StarryRTX @jerry1717 %%%