普通treap36pts求调

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+3,inf=0x3f3f3f3f;
struct node{
	int l,r,val,pri,cnt,siz; 
	//l,r是两个儿子，val是权值，pri是优先级，cnt是重数，siz是子树大小 
}t[maxn];
int n,k,x,y,ans,root,tot,op; 
void zig(int &k){ //右旋 
	int y=t[k].l; //y为左子结点 
	t[k].l=t[y].r;
	t[y].r=k; //交换y和k的父子位置 
	t[k].siz=t[t[k].l].siz+t[t[k].r].siz+t[k].cnt; //更新size 
	t[y].siz=t[t[y].l].siz+t[t[y].r].siz+t[y].cnt; //维护size
	k=y;
}
void zag(int &k){ //左旋 
	int y=t[k].r;
	t[k].r=t[y].l;
	t[y].l=k;
	t[k].siz=t[t[k].l].siz+t[t[k].r].siz+t[k].cnt;
	t[y].siz=t[t[y].l].siz+t[t[y].r].siz+t[y].cnt;
	k=y;
}
void Insert(int &k,int &p){
	if(!k){
		k=++tot;t[k].val=p;t[k].pri=rand(); //随机优先级 
		t[k].cnt=t[k].siz=1;
		t[k].l=t[k].r=0; //新建结点 
		return;
	}
	else ++t[k].siz;
	if(t[k].val==p) ++t[k].cnt; //重复元素 
	else if(t[k].val>p){
		Insert(t[k].l,p);
		if(t[t[k].l].pri<t[k].pri) zig(k); //左旋维护堆序 
	}
	else{
		Insert(t[k].r,p);
		if(t[t[k].r].pri<t[k].pri) zag(k); //右旋维护堆序 
	}
	return;
}
void Delete(int &k,int &p){
	if(t[k].val==p){
		if(t[k].cnt>1) t[k].cnt--,t[k].siz--; //重复元素
		else if(!t[k].l||!t[k].r) k=t[k].l+t[k].r;
		else if(t[t[k].l].pri<t[t[k].r].pri) zig(k),Delete(k,p);
		else zag(k),Delete(k,p);
		return;
	}
	t[k].siz--;
	if(p<t[k].val) Delete(t[k].l,p);
	else Delete(t[k].r,p);
	return;
} 
int QueryPre(int &p){
	int x=root,res=-inf;
	while(x){
	    if(t[x].val<=p) res=t[x].val,x=t[x].r;
	    else x=t[x].l; 
    }   
    return res;
}
int QuerySuc(int &p){
	int x=root,res=inf;
	while(x){
	    if(t[x].val>=p) res=t[x].val,x=t[x].l;
	    else x=t[x].r; 
    }   
    return res;
}
int QueryKth(int &k){
	int x=root;
	while(x){
		if(t[t[x].l].siz<k&&t[t[x].l].siz+t[x].cnt>=k) return t[x].val; //第k个是x 
		if(t[t[x].l].siz>=k) x=t[x].l; //第k个在左边 
		else k-=(t[t[x].l].siz+t[x].cnt),x=t[x].r; //第k个在右边 
	}
	return -1; //找不到 
}
int QueryRank(int &p){
	int x=root,res=0;
	while(x){
		if(t[x].val==p) return res+t[t[k].l].siz+1; //找到该元素 
		if(p<t[x].val) x=t[x].l;
		else res+=t[t[x].l].siz+t[x].cnt,x=t[x].r;
	}
	return res;
}
int main(){
	srand(time(NULL));
	cin >> n;
	while(n--){
		cin >> op >> x;
		if(op==1) Insert(root,x);
		else if(op==2) Delete(root,x);
		else if(op==3) cout << QueryRank(x) << endl;
		else if(op==4) cout << QueryKth(x) << endl;
		else if(op==5) cout << QueryPre(x) << endl;
		else if(op==6) cout << QuerySuc(x) << endl;
	}
	return 0;
}