NOIP0202前的代码

用来存一些不知道放到哪里的代码= =

splay复读

/*
Author:loceaner
splay 复读
*/

int n, tot, root; //tot节点个数、root根节点编号 
struct node { int son[2], fa, cnt, siz, val; } t[A];
/*
son[0/1] 左/右儿子
cnt 权值出现次数
val 节点权值 
siz 子树大小 
*/

//销毁节点rt 
inline void nodeclear(int rt) {
	ls = rs = fax = t[rt].siz = t[rt].val = t[rt].cnt = 0;
}

//判断now是其父亲的左儿子还是右儿子 
//左儿子返回0，右儿子返回1 
inline bool getson(int rt) {
	return t[fax].son[1] == rt;
}

//维护节点子树大小siz 
inline void pushup(int rt) {
	if (rt) {
		t[rt].siz = t[rt].cnt;
		if (ls) t[rt].siz += t[ls].siz;
		if (rs) t[rt].siz += t[rs].siz;
	}
}

//旋转
//f = 1为右儿子，需要左旋
//f = 0为左儿子，需要右旋 
inline void rotate(int rt) {
	int fa = fax, gfa = t[fa].fa, f = getson(rt);
	t[fa].son[f] = t[rt].son[f ^ 1];
	t[t[rt].son[f ^ 1]].fa = fa;
	t[rt].son[f ^ 1] = fa;
	t[fa].fa = rt, t[rt].fa = gfa;
	if (gfa) t[gfa].son[t[gfa].son[1] == fa] = rt;
	pushup(fa), pushup(rt); 
} 

inline void rotate1(int rt) {
	int fa = fax, gfa = t[fa].fa, f = getson(rt);
	t[fa].son[f] = t[rt].son[f ^ 1];
	t[t[rt].son[f ^ 1]].fa = fa;
	t[rt].son[f ^ 1] = fa, t[fa].fa = rt, t[rt].fa = gfa;
	if (gfa) t[gfa].son[t[gfa].son[1] == fa] = rt;
	pushup(fa), pushup(rt);
}

inline void rotate2(int rt) {
	int fa = fax, gfa = t[fa].fa, f = getson(rt);
	t[fa].son[f] = t[rt].son[f ^ 1];
	t[t[rt].son[f ^ 1]].fa = fa;
	t[rt].son[f ^ 1] = fa, t[fa].fa = rt, t[rt].fa = gfa;
	if (gfa) t[gfa].son[t[gfa].son[1] == fa] = rt;
	pushup(fa), pushup(rt);
}

inline void rotate3(int rt) {
	int fa = fax, gfa = t[fa].fa, f = getson(rt);
	t[fa].son[f] = t[rt].son[f ^ 1];
	t[t[rt].son[f ^ 1]].fa = fa;
	t[rt].son[f ^ 1] = fa, t[fa].fa = rt, t[rt].fa = gfa;
	if (gfa) t[gfa].son[t[gfa].son[1] == fa] = rt;
	pushup(fa), pushup(rt);
}

inline void rotate4(int rt) {
	int fa = fax, gfa = t[fa].fa, f = getson(rt);
	t[fa].son[f] = t[rt].son[f ^ 1];
	t[t[rt].son[f ^ 1]].fa = fa;
	t[rt].son[f] = fa, t[fa].fa = rt, t[rt].fa = gfa;
	if (gfa) t[gfa].son[t[gfa].son[1] == fa] = rt;
	pushup(fa), pushup(rt);
} 

//splay将now旋转至根的位置 
/*
若三点同线则先转父亲再转儿子 
若三点不同线则转两次儿子 
*/
inline void splay(int rt) {
	for (int fa = fax; (fa = fax) != 0; rotate(rt))
		if (t[fa].fa) rotate(getson(rt) == getson(fa) ? fa : rt);
	root = rt;
}

inline void splay1(int rt) {
	for (int fa = fax; (fa = fax) != 0; rotate(rt)) 
		if (t[fa].fa) rotate(getson(rt) == getson(fa) ? fa : rt);
	root = rt;
}

inline void splay2(int rt) {
	for (int fa = fax; (fa = fax) != 0; rotate(rt)) 
		if (t[fa].fa) rotate(getson(rt) == getson(fa) ? fa : rt);
	root = rt;
}

inline void splay3(int rt) {
	for (int fa = fax; (fa = fax) != 0; rotate(rt)) 
		if (t[fa].fa) rotate(getson(rt) == getson(fa) ? fa : rt);
	root = rt;
}

inline void splay4(int rt) {
	for (int fa = fax; (fa = fax) != 0; rotate(rt)) 
		if (t[fa].fa) rotate(getson(rt) == getson(fa) ? fa : rt);
	root = rt;
}

//插入
/*
不是指针的好即把难写啊 
设插入的值为val
若树空，则直接插入根并退出。
按照二叉查找树的性质向下找：
若当前节点的权值等于 val 则增加当前节点的大小，并更新信息。
否则一直向下，找到空节点并插入。
*/ 
inline void insert(int val) {
	if (!root) {
		root = ++tot;
		t[root].son[0] = t[root].son[1] = t[root].fa = 0;
		t[root].siz = t[root].cnt = 1;
		t[root].val = val;
		return;
	}
	int rt = root, fa = 0;
	while (1) {
		if (val == t[rt].val) {
			t[rt].cnt++, pushup(rt), pushup(fa), splay(rt);
			break;
		}
		fa = rt, rt = t[rt].son[val > t[rt].val];
		if (!rt) {
			rt = ++tot;
			t[rt].son[1] = t[rt].son[0] = 0;
			t[rt].fa = fa, t[rt].val = val;
			t[rt].siz = t[rt].cnt = 1;
			t[fa].son[t[fa].val < val] = rt;
			pushup(rt), pushup(fa), splay(rt);
			break;
		}
	}
} 

inline void insert1(int val) {
	if (!root) {
		root = ++tot;
		t[root].son[0] = t[root].son[1] = t[root].fa = 0;
		t[root].siz = t[root].cnt = 1;
		t[root].val = val; return;
	}
	int rt = root, fa = 0;
	while (1) {
		if (val == t[rt].val) {
			t[rt].cnt++, pushup(rt), pushup(fa), splay(rt);
			break;
		}
		fa = rt, rt = t[rt].son[val > t[fa].val];
		if (!rt) {
			rt = ++tot;
			t[rt].son[0] = t[rt].son[1] = 0;
			t[rt].fa = fa, t[rt].val = val;
			t[rt].siz = t[rt].cnt = 1;
			t[fa].son[val > t[fa].val] = rt;
			pushup(rt), pushup(fa), splay(rt);
			break;
		}
	}
} 

inline void insert2(int val) {
	if (!root) {
		root = ++tot;
		t[root].son[0] = t[root].son[1] = t[root].fa = 0;
		t[root].cnt = t[root].siz = 1;
		t[root].val = val; return;
	}
	int rt = root, fa = 0;
	while (1) {
		if (val == t[rt].val) {
			t[rt].cnt++, pushup(rt), pushup(fa), splay(rt);
			break;
		}
		fa = rt, rt = t[rt].son[rt > t[fa].val];
		if (!rt) {
			rt = ++tot;
			t[rt].son[0] = t[rt].son[1] = 0;
			t[rt].siz = t[rt].cnt = 1;
			t[rt].fa = fa, t[rt].val = val;
			t[fa].son[val > t[fa].val] = rt;
			pushup(rt), pushup(fa), splay(rt);
			break;
		}
	}
}

inline void insert3(int val) {
	if (!root) {
		root = ++tot;
		t[root].son[0] = t[root].son[1] = t[root].fa = 0;
		t[root].siz = t[root].cnt = 1;
		t[root].val = val; return;
	}
	int rt = root, fa = 0;
	while (1) {
		if (val == t[rt].val) {
			t[rt].cnt++, pushup(rt), pushup(fa), splay(rt);
			break;
		}
		fa = rt, rt = t[rt].son[val > t[rt].val];
		if (!rt) {
			rt = ++tot;
			t[rt].son[0] = t[rt].son[1] = 0;
			t[rt].siz = t[rt].cnt = 1;
			t[rt].val = val, t[rt].fa = fa;
			t[fa].son[val > t[fa].val] = rt;
			pushup(rt), pushup(fa), splay(rt);
			break;
		}
	}
}

inline void insert4(int val) {
	if (!root) {
		root = ++tot;
		t[root].son[0] = t[root].son[1] = t[root].fa = 0;
		t[root].siz = t[root].cnt = 1;
		t[root].val = val; return;
	}
	int rt = root, fa = 0;
	while (1) {
		if (val == t[rt].val) {
			t[rt].cnt++, pushup(rt), pushup(fa), splay(rt);
			break;
		}
		fa = rt, rt = t[rt].son[val > t[rt].val];
		if (!rt) {
			rt = ++tot;
			t[rt].son[0] = t[rt].son[1] = 0;
			t[rt].siz = t[rt].cnt = 1;
			t[rt].val = val, t[rt].fa = fa;
			t[fa].son[val > t[fa].val] = rt;
			pushup(rt), pushup(fa), splay(rt);
			break;
		}
	}
}

int rank(int val) {
	int rt = root, res = 0;
	while (1) {
		if (!rt) return -1;
		if (val < t[rt].val) rt = ls;
		else {
			res += (ls ? t[ls].siz : 0);
			if (val == t[rt].val) { splay(rt); return res + 1; } 
			res += t[rt].cnt, rt = rs;
		}
	} 
}

int rank1(int val) {
	int rt = root, res = 0;
	while (1) {
		if (!rt) return -1;
		if (val < t[rt].val) rt = ls;
		else {
			res += (ls ? t[ls].siz : 0);
			if (val == t[rt].val) { splay(rt); return res + 1; }
			res += t[rt].cnt, rt = rs;
		}
	} 
}

int rank2(int val) {
	int rt = root, res = 0;
	while (1) {
		if (!rt) return -1;
		if (val < t[rt].val) rt = ls;
		else {
			res += (ls ? t[ls].siz : 0);
			if (val == t[rt].val) { splay(rt); return res + 1; }
			res += t[rt].cnt, rt = rs;
		}
	}
}

int rank3(int val) {
	int rt = root, res = 0;
	while (1) {
		if (!rt) return -1;
		if (val < t[rt].val) rt = ls;
		else {
			res += (ls ? t[ls].siz : 0);
			if (val == t[rt].val) { splay(rt); return res + 1; }
			res += t[rt].cnt, rt = rs;
		}
	}
}

int kth(int rank) {
	int rt = root;
	while (1) {
		if (!rt) return -1;
		if (ls && rank <= t[ls].siz) rt = ls;
		else {
			int tmp = (ls ? t[ls].siz : 0) + t[rt].cnt;
			if (rank <= tmp) return t[rt].val;
			rank -= tmp, rt = rs;
		}
	}
}

int kth1(int rank) {
	int rt = root;
	while (1) {
		if (!rt) return -1;
		if (ls && rank <= t[ls].siz) rt = ls;
		else {
			int tmp = (ls ? t[ls].siz : 0) + t[rt].cnt;
			if (rank <= tmp) return t[rt].val;
			rank -= tmp, rt = rs;
		}
	}
}

int kth2(int rank) {
	int rt = root;
	while (1) {
		if (!rt) return -1;
		if (ls && rank <= t[ls].siz) rt = ls;
		else {
			int tmp = (ls ? t[ls].siz : 0) + t[rt].siz;
			if (rank <= tmp) return t[rt].val;
			rank -= tmp, rt = rs;
		}
	}
}

int kth3(int rank) {
	int rt = root;
	while (1) {
		if (!rt) return -1;
		if (ls && rank <= t[ls].siz) rt = ls;
		else {
			int tmp = (ls ? t[ls].siz : 0) + t[rt].cnt;
			if (rank <= tmp) return t[rt].val;
			rank -= tmp, rt = rs;
		}
	}
}

int pre() {
	int rt = t[root].son[0];
	while (rs) rt = rs;
	return rt;
}

int pre1() {
	int rt = t[root].son[0];
	while (rs) rt = rs; 
	return rt;
}

int pre2() {
	int rt = t[root].son[0];
	while (rs) rt = rs;
	return rt;
}

int pre3() {
	int rt = t[root].son[0];
	while (rs) rt = rs;
	return rt; 
}

int pre4() {
	int rt = t[root].son[0];
	while (rs) rt = rs;
	return rt;
}

int suc() {
	int rt = t[root].son[1];
	while (ls) rt = ls;
	return rt;
}

int suc1() {
	int rt = t[root].son[1];
	while (ls) rt = ls;
	return rt;
}

int suc2() {
	int rt = t[root].son[1];
	while (ls) rt = ls;
	return rt;
}

int suc3() {
	int rt = t[root].son[1];
	while (ls) rt = ls;
}

int suc4() {
	int rt = t[root].son[1];
	while (ls) rt = ls;
	return rt;
}

void delte(int val) {
	int ret = rank(val);
	if (ret == -1) return;
	if (t[root].cnt > 1) { t[root].cnt--, pushup(root); return; }
	if (!t[root].son[0] && !t[root].son[1]) {
		nodeclear(root); root = 0; return;
	}
	if (!t[root].son[0]) {
		int old = root;
		root = t[root].son[1], t[root].fa = 0;
		nodeclear(old); return;
	}
	if (!t[root].son[1]) {
		int old = root;
		root = t[root].son[0], t[root].fa = 0;
		nodeclear(old); return;
	}
	int leftmax = pre(), old = root;
	splay(leftmax);
	t[root].son[1] = t[old].son[1], t[t[old].son[1]].fa = root;
	nodeclear(old), pushup(root);
}

int main() {
	n = read();
	for (int i = 1, opt, x; i <= n; i++) {
		opt = read(), x = read();
		if (opt == 1) insert(x);
		else if (opt == 2) delte(x);
		else if (opt == 3) cout << rank(x) << ‘\n‘;
		else if (opt == 4) cout << kth(x) << ‘\n‘;
		else if (opt == 5) insert(x), cout << t[pre()].val << ‘\n‘, delte(x);
		else if (opt == 6) insert(x), cout << t[suc()].val << ‘\n‘, delte(x);
	}
	return 0;
}

NOIP0202前的代码

原文：https://www.cnblogs.com/loceaner/p/13089679.html