Treap的模板题65pts, 错 #8 ~ #12测试点点

有没有哪位大佬和我错了同样的测试点的，求调

在线等， 急

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

const int INF = 0x7fffffff;
const int N = 100010;
int n, root, tot;
struct Treap {
	int l, r;
	int val, dat; 
	int cnt, size;
} t[N];

void cprintf(int p) {
	cout << p << " " << t[p].cnt << " " << t[p].size << " " << t[p].val << endl;
}

int New(int val) {
	t[++tot].val = val;
	t[tot].dat = rand();
	t[tot].cnt = t[tot].size = 1;
	return tot;
}

void update(int p) {
	t[p].size = t[t[p].l].size + t[t[p].r].size + t[p].cnt;
}

void build() {
	New(-INF), New(INF);
	root = 1, t[1].r = 2;
	update(root);
	update(t[root].r);
}

void turn_left(int &p) {
	int q = t[p].r;
	t[p].r = t[q].l;
	t[q].l = p;
	p = q;
	update(t[p].l);
	update(p);
}

void turn_right(int &p) {
	int q =  t[p].l;
	t[p].l = t[q].r;
	t[q].r = p;
	p = q;
	update(t[p].r);
	update(p);
}

void insert(int &p, int val) {
	if (p == 0) {             																		//到一个空节点 
		p = New(val);																				//建立一个新节点 																				
		return;
	} if (t[p].val == val) {																		//重复，cnt++即可 
		t[p].cnt++;
		update(p);																					//cnt更新，size也要更新 
		return;
	} if (val < t[p].val) {																			//往左子树
		insert(t[p].l, val);								 
		if (t[t[p].l].dat > t[p].dat) turn_right(p); 												//维护堆性质 
	} else {																						//右子树同理 
		insert(t[p].r, val);
		if (t[t[p].r].dat > t[p].dat) turn_left(p); 
	}
	update(p);																						//递归向上更新 
}

void remove(int &p, int val) {	
//	cprintf(p);		
	if (p == 0) return;																				//没有val 
	if (t[p].val == val) {
		if (t[p].cnt > 1) {																			//重复，cnt--即可 
			t[p].cnt--;
			update(p);																				//cnt更新，size也要更新 
			return;
		} if (t[p].l != 0 or t[p].r != 0) {
			if (t[p].r == 0 or t[t[p].l].dat > t[t[p].r].dat) turn_right(p), remove(t[p].r, val);	//维护堆性质 
			else turn_left(p), remove(t[p].l, val);
			update(p);																				//改变树结构，更新 		
		} else p = 0; 																				//叶子结点，直接删除
		return;
	}
	val < t[p].val ? remove(t[p].l, val) : remove(t[p].r, val);										//找 
	update(p);																						//自底向上更新 
//	cprintf(p);																					
}

int grbv(int p, int val) {
	if (p == 0) return 1;
	if (val == t[p].val) return t[t[p].l].size + 1;													//找到，返回左子树的个数+1 
	if (val < t[p].val) return grbv(t[p].l, val);													//val在左子树， 递归 
	return t[t[p].l].size + t[p].cnt + grbv(t[p].r, val); 											//val在右子树，返回左子树的个数+p的副本数量+右子树递归 
}

int gvbr(int p, int rank) {
	if (p == 0) {
//		cout << t[root].size << " " << rank << endl;
		return INF;
	}
	if (t[t[p].l].size >= rank) return gvbr(t[p].l, rank);											//val被包含在左子树 
	if (t[t[p].l].size + t[p].cnt >= rank) return t[p].val;											//val是p的副本中的一个 
	return gvbr(t[p].r, rank - t[t[p].l].size - t[p].cnt);											//val在右子树, 只找排名为rank-t[t[p].l].size-t[p].cnt的val 
}

int get_pre(int val) {
	int ans = 1;
	int p = root;
	while (p != 0) {
		if (t[p].val == val) {   																	//找到 
			if (t[p].l > 0) {																		//非空	
				p = t[p].l;																			//赋值为左子树 
				while(t[p].r > 0) {  																//左子树一直向右找 
					p = t[p].r;
				}
				ans = p;																			//更新ans 
			}
			break;
		}
		if (val > t[p].val and t[p].val > t[ans].val)  ans = p;										//如果是右子树，它的前驱可能为当前的根节点 
		p = val < t[p].val ? t[p].l : t[p].r;  														//找val 
	}
	return t[ans].val;
}

int get_next(int val) {
	int ans = 2;
	int p = root;
	while (p != 0) {
		if (t[p].val == val) {    																	//找到 
			if (t[p].r > 0) {																		//非空
				int p = t[p].r;																		//赋值为右子树 
				while(t[p].l > 0) { 																//右子树一直向左找 
					p = t[p].l;
				}
				ans = p;																			//更新ans 
			}
			break;
		}
		if (val < t[p].val and t[p].val < t[ans].val)  ans = p;										//如果是左子树，它的后继可能为当前的根节点 
		p = val < t[p].val ? t[p].l : t[p].r;  														//找val 
	}
	return t[ans].val;
}

int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	build();
	while (n--) {
		int opt, x;
		cin >> opt >> x;
		switch (opt) {
			case 1:
				insert(root, x);
				break;
			case 2:
				remove(root, x);
				break;
			case 3:
				cout << grbv(root, x) - 1 << endl;
				break;
			case 4:
				cout << gvbr(root, x + 1) << endl;
				break;
			case 5:
				cout << get_pre(x) << endl;
				break;
			case 6:
				cout << get_next(x) << endl;
				break;
		}
//		cout << t[root].size << endl;
	}
	return 0;
}