Record: https://www.luogu.com.cn/record/171507329

Code:

#include<bits/stdc++.h>
using namespace std;
struct node{
	node *l,*r;
	int val,fix,weight;
	int size,lsize,rsize;
};
void Update_Size(node*& root){
	if(root==NULL) return;
	int ans=1;
	Update_Size(root->l);
	if(root->l!=NULL) ans+=root->l->size;
	Update_Size(root->r);
	if(root->r!=NULL) ans+=root->r->size;
	root->size=ans;
}
node* Find_Node(node*& root,int v){
	if(root==NULL) return NULL;
	if(root->val==v) return root;
	else if(v<root->val) return Find_Node(root->l,v);
	else return Find_Node(root->r,v);
}
void Left_Rotate(node* root){
	node* tmp=root->r;
	root->r=tmp->l;
	tmp->l=root;
	root=tmp;
	Update_Size(root);
}
void Right_Rotate(node* root){
	node* tmp=root->l;
	root->l=tmp->r;
	tmp->r=root;
	root=tmp;
	Update_Size(root);
}
void Treap_Insert(node*& root,int v){
	if(Find_Node(root,v)!=NULL){
		Find_Node(root,v)->weight++;
		Update_Size(root);
		return;
	}
	if(root==NULL){
		root=new node();
		root->l=NULL,root->r=NULL;
		root->val=v;
		root->weight=1;
		srand(time(0));
		root->fix=rand();
		Update_Size(root);
		return;
	}
	if(v<root->val){
		Treap_Insert(root->l,v);
		if(root->l->fix<root->fix) Right_Rotate(root);
	}
	else if(v>root->val){
		Treap_Insert(root->r,v);
		if(root->r->fix<root->fix) Left_Rotate(root);
	}
	Update_Size(root);
}
void Treap_Delete(node*& root,int v){
	if(Find_Node(root,v)->weight>0){
		Find_Node(root,v)->weight--;
		Update_Size(root);
		return;
	}
	if(root->val!=v){
		if(v<root->val) Treap_Delete(root->l,v);
		else Treap_Delete(root->r,v);
		return;
	}
	node* tmp=root;
	if(root->l==NULL&&root->r==NULL){
		delete root;
		return;
	}
	if(root->l==NULL&&root->r!=NULL) tmp->l=root->r->l,tmp->r=root->r->r,root=tmp;
	if(root->l!=NULL&&root->r==NULL) tmp->l=root->l->l,tmp->r=root->l->r,root=tmp;
	if(root->l!=NULL&&root->r!=NULL){
		if(root->l->fix<root->r->fix){
			Right_Rotate(root);
			Treap_Delete(root->r,v);
		}else{
			Left_Rotate(root);
			Treap_Delete(root->l,v);
		}
	}
	Update_Size(root);
}
node* Find_Prev(node* root,int v){
	node* tmp=new node();
	node* now=root;
	tmp=NULL;
	while(now!=NULL){
		if(now->val<=v){
			tmp=now;
			now=now->r;
		}else now=now->l;
	}
	return tmp;
}
node* Find_Next(node* root,int v){
	node* tmp=new node();
	node* now=root;
	tmp=NULL;
	while(now!=NULL){
		if(now->val>=v){
			tmp=now;
			now=now->l;
		}else now=now->r;
	}
	return tmp;
}
int Get_The_Kth_Node(node*& root,int k){
	int tmp=root->l==NULL?0:root->l->size;
	if(k<=tmp) return (root->l==NULL?1:Get_The_Kth_Node(root->l,k));
	else if(k<=tmp+root->weight) return root->val;
	else return (root->r==NULL?1:Get_The_Kth_Node(root->r,k-(tmp+root->weight)));
	return -1;
}
int Get_Rank(node*& root,int v){
	int tmp=root->l==NULL?0:root->l->size;
	if(v==root->val) return tmp+1;
	else if(v<root->val) return (root->l==NULL?1:Get_Rank(root->l,v));
	else return (root->r==NULL?root->size+1:tmp+root->weight+Get_Rank(root->r,v));
}
int n,cmd,t;
node* root;
int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%d%d",&cmd,&t);
		if(cmd==1) Treap_Insert(root,t);
		if(cmd==2) Treap_Delete(root,t);
		if(cmd==3) printf("%d\n",Get_Rank(root,t));
		if(cmd==4) printf("%d\n",Get_The_Kth_Node(root,t));
		if(cmd==5) printf("%d\n",Find_Prev(root,t)->val);
		if(cmd==6) printf("%d\n",Find_Next(root,t)->val);
	}
}

貌似是 Get_Rank 函数有问题。