题目传送门

使用了FHQ-treap 100分的是旋转treap

有误代码如下：

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

const int Tree_Size_Max = 1e5 + 10;


struct TREE{
	int siz;
	TREE* left;
	TREE* right;
	int val;
	int ran;
	
	// TREE operator=(const TREE *tp){
	// 	siz = tp -> siz;
	// 	left = tp -> left;
	// 	right = tp -> right;
	// 	val = tp -> val;
	// 	count = tp -> count;
	// }
	// TREE(){}
	TREE(int val):
		siz(1),left(nullptr),right(nullptr),val(val),ran(rand()){}
};

TREE* root = nullptr;
// TREE tree[Tree_Size_Max];

void upd_siz(TREE *x){
	if (!x) return;
	x->siz = 1;
	x->siz +=  x -> left ? x-> left -> siz : 0;
	x->siz +=  x-> right ? x -> right -> siz : 0;
}

// TREE* new_TREE(int x){
// 	sz++;
// //	tree[sz].count = 1;
// 	tree[sz].left = nullptr;
// 	tree[sz].right = nullptr;
// 	tree[sz].ran = rand();
// 	tree[sz].siz = 1;
// 	tree[sz].val = x;
// 	return &tree[sz];
// }

void split(TREE* &now, int k, TREE* &x, TREE* &y){
	if(now == nullptr){
		x = y = nullptr;
		return;
	}
	if(now -> val <= k){
		x = now;
		split(now -> right, k, x -> right, y);
		upd_siz(x);
	}else{
		y = now;
		split(now -> left , k, x, y -> left );
		upd_siz(y);
	}
}

TREE* merge(TREE *x, TREE *y){
	// if(x == nullptr && y == nullptr) return nullptr;
	if(x == nullptr) return y;
	if(y == nullptr) return x;
	
	
	if(x -> ran > y -> ran){
		x -> right = merge(x -> right, y);
		upd_siz(x);
		return x; 
	}
	else{
		y -> left = merge(x, y -> left);
		upd_siz(y);
		return y;
	}
}

void preOrder(TREE* rt){
	if(!rt) return;
	printf("%d ",rt -> val);
	preOrder(rt -> left);
	preOrder(rt ->  right);
}

void inOrder(TREE* rt){
	if(!rt) return;
	inOrder(rt -> left);
	printf("%d ",rt -> val);
	inOrder(rt -> right);
}

void insert(int x){
	TREE *a;
	TREE *b;
	TREE* NewTree = new TREE(x);
	split(root, x, a, b);
	root = merge(merge(a, NewTree) , b);
	
	
//	preOrder(root),printf("\n");
//	inOrder(root),printf("\n");
}

void del(int x){
	TREE* a;
	TREE* b;
	TREE* c;
	split(root, x, a, b);
	split(a, x-1, a, c);
	c = merge(c -> left, c -> right);
	root = merge( merge( a, c), b);
}

void rnk(int x){
	TREE* a;
	TREE* b;
	split(root, x-1, a, b);
	printf("%d\n", a ? a -> siz + 1 : 1);
	root = merge(a, b);
}

TREE* kth(TREE* now, int k){
	if(!now) return nullptr;
	// while(1){
	// 	if(now -> left -> siz >= k){
	// 		now = now -> left;
	// 	}else if(now -> left -> siz + 1 == k){
	// 		printf("%d\n", now -> val);
	// 		return;
	// 	}else{
	// 		k -= now -> left -> siz + 1;
	// 		now = now -> right;
	// 	}
	// }
	int left_size= now->left ? now->left->siz : 0;
	if(k==left_size+1) return now;
	else if(k<left_size+1) return kth(now->left,k);
	else return kth(root->right,k-left_size-1); // rank>left_size+1 
}

void pre(int x){
	TREE* a;
	TREE* b;
	split(root, x-1, a, b);
	TREE* temp = kth(a, a -> siz);
	root = merge(a, b);
	printf("%d\n", temp ? temp -> val : 0);
	return;
}

void nxt(int x){
	TREE* a;
	TREE* b;
	split(root, x, a, b);
	TREE* temp = kth(b, 1);
	root = merge(a, b);
	printf("%d\n",temp ? temp -> val : 0);
	return;
}

int main(){
	int n;
	int opt;
	int x;
	// srand((unsigned) time (NULL));
	
	scanf("%d",&n);
	TREE* temp;
	while(n--){
		scanf("%d %d",&opt,&x);
		if(opt==1) insert(x);
		if(opt==2) del(x);
		if(opt==3) rnk(x);
		if(opt==4) temp = kth(root,x),printf("%d\n", temp ? temp -> val : 0);
		if(opt==5) pre(x);
		if(opt==6) nxt(x);
	}
	return 0;
}