有旋 Treap MLE [37,51] pts 求调

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int maxn=1e5+10;
int n,op,x,root,cnt;
struct Treap{
	int ls,rs;
	int val,pri;
	int size;
	#define lson t[p].ls
	#define rson t[p].rs
}t[maxn];
void build(int x){
	cnt++;
	t[cnt].ls=t[cnt].rs=0;
	t[cnt].val=x;
	t[cnt].size=1;
	t[cnt].pri=rand();
}
void pushup(int p){
	t[p].size=t[lson].size+t[rson].size+1;
}
#define lft 1
#define rgh 0
void rotate(int &p,int d){
	int k;
	if(d==lft){
		k=t[p].rs;
		t[p].rs=t[k].ls;
		t[k].ls=p;
	}else{
		k=t[p].ls;
		t[p].ls=t[k].rs;
		t[k].rs=p;
	}
	t[k].size=t[p].size;
	pushup(p);
	p=k;
}
void insert(int &p,int x){
	if(!p){
		build(x);
		p=cnt;//
		return;
	}
	t[p].size++;
	if(x>=t[p].val)insert(rson,x);
	else insert(lson,x);
	if(t[p].ls&&t[p].pri<t[lson].pri)rotate(p,rgh);
	if(t[p].rs&&t[p].pri<t[rson].pri)rotate(p,lft);
	pushup(p);
}
void del(int &p,int x){
	t[p].size--;
	if(t[p].val==x){
		if(!t[p].ls&&!t[p].rs){p=0;return;}
		if(!t[p].ls||!t[p].rs){p=t[p].ls+t[p].rs;return;}
		if(t[lson].pri>t[rson].pri){
			rotate(p,rgh);
			del(lson,x);
		}else{
			rotate(p,lft);
			del(rson,x);
		}
		return;
	}
	if(t[p].val>x)del(lson,x);
	else del(rson,x);
	pushup(p);
}
int rk(int p,int x){
	if(!p)return 0;
	if(t[p].val<x)return t[lson].size+1+rk(rson,x);
	return rk(lson,x);
}
int kth(int p,int k){
	if(k==t[lson].size+1)return t[p].val;
	if(k>t[lson].size+1)return kth(rson,k-t[lson].size-1);
	if(k<t[lson].size+1)return kth(lson,k);
}
int pre(int p,int x){
	if(!p)return 0;
	if(t[p].val>=x)return pre(lson,x);
	int tmp=pre(rson,x);
	if(!tmp)return t[p].val;
	return tmp;
}
int nxt(int p,int x){
	if(!p)return 0;
	if(t[p].val<=x)return nxt(rson,x);
	int tmp=nxt(lson,x);
	if(!tmp)return t[p].val;
	return tmp;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	srand(time(NULL));
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>op>>x;
		if(op==1)insert(root,x);
		if(op==2)del(root,x);
		if(op==3)cout<<rk(root,x)+1<<"\n";
		if(op==4)cout<<kth(root,x)<<"\n";
		if(op==5)cout<<pre(root,x)<<"\n";
		if(op==6)cout<<nxt(root,x)<<"\n";
	}
	return 0;
}
/*
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

*/