rt

此为提交记录

悬赏一关注

代码：

#include<bits/stdc++.h>
#define int long long
#define maxn 100005
#define mod 998244353 
using namespace std;
struct Node{
	int dat;
	int val;
	int l,r;
	int size;
	int cnt;
}t[maxn];
int n,tot=0,root;
int New(int v){
	t[++tot].val=v;
	t[tot].dat=rand()%mod;
	t[tot].size=1;
	t[tot].cnt=1;
	return tot;
}
void pushup(int u){
	t[u].size=t[t[u].l].size+t[t[u].r].size+t[u].cnt;
}
void build(){
	root=New(LONG_LONG_MIN);
	t[root].r=New(LONG_LONG_MAX);
	pushup(root);
}
//
void R_Rotate(int &u){
	int temp=t[u].l;
	t[u].l=t[temp].r;
	t[temp].r=u;
	u=temp;
	pushup(t[u].r);
	pushup(u); 
}
void L_Rotate(int &u){
	int temp=t[u].r;
	t[u].r=t[temp].l;
	t[temp].l=u;
	u=temp;
	pushup(t[u].l);
	pushup(u);
}
//
void insert(int &u,int v){
	if(!u){
		u=New(v);
		return;
	}
	if(v==t[u].val){
		t[u].cnt++;
	}else{
		if(v<t[u].val){
			insert(t[u].l,v);
			if(t[u].dat<t[t[u].l].dat) R_Rotate(u);
		}else{
			insert(t[u].r,v);
			if(t[u].dat<t[t[u].r].dat) L_Rotate(u);
		}
		pushup(u);
	}
}
void Remove(int &u,int v){
	if(!u) return;
	if(t[u].val==v){
		if(t[u].cnt>1){
			t[u].cnt--;
			pushup(u);
			return;
		}
		if(t[u].l||t[u].r){
			if(!t[u].r||t[t[u].l].dat>t[t[u].r].dat){
				L_Rotate(u);
				Remove(t[u].l,v);
			}else{
				R_Rotate(u);
				Remove(t[u].r,v);
			}
			pushup(u);
		}else{
			u=0;
		}
		return;
	}
	if(v<t[u].val){
		Remove(t[u].l,v);
	}else{
		Remove(t[u].r,v);
	}
	pushup(u); 
}
//void BST(int u){
//	if(u==0) return;
//	cout<<"JZYAKIOI'SBST: "<<t[u].val<<' '<<t[t[u].l].val<<' '<<t[t[u].r].val<<endl;
//	BST(t[u].l);
//	BST(t[u].r);
//}
int get_rank(int u,int v){
	if(u==0){
		return 0;
	}
	if(t[u].val==v){
		return t[t[u].l].size+1;
	}else if(v<t[u].val){
		return get_rank(t[u].l,v);
	}else{
		return t[t[u].l].size+t[u].cnt+get_rank(t[u].r,v);
	}
}
int get_val(int u,int rank){
	if(!u){
		return INT_MAX;
	}
	if(rank<=t[t[u].l].size){
		return get_val(t[u].l,rank);
	}else if(rank<=t[t[u].l].size+t[u].cnt){
		return t[u].val;
	}else{
		return get_val(t[u].r,rank-t[t[u].l].size-t[u].cnt);
	}
}
int get_pre(int v){
	int u=root,pre;
	while(u){
		if(t[u].val<v){
			pre=t[u].val;
			u=t[u].r;
		}else{
			u=t[u].l;
		}
	}
	return pre;
}
int get_next(int v){
	int u=root,next=root;
	while(u){
		if(t[u].val>v){
			next=t[u].val;
			u=t[u].l;
		}else{
			u=t[u].r;
		}
	}
	return next;
}
signed main(){
	srand(time(0));
	build();
	cin>>n;
	for(int i=1;i<=n;i++){
		int op,x;
		cin>>op>>x;
		if(op==1) insert(root,x);
		else if(op==2) Remove(root,x);
		else if(op==3) cout<<get_rank(root,x)-1<<endl;
		else if(op==4) cout<<get_val(root,x+1)<<endl;
		else if(op==5) cout<<get_pre(x)<<endl;
		else if(op==6) cout<<get_next(x)<<endl;
//		BST(root);
//		if(op==1){
//			for(int i=1;i<=n;i++){
//				cout<<get_rank(root,i)-1<<' ';
//			}
//			cout<<endl;
//		}
	}
	return 0;
}

另附 #3数据