测试结果

#include<bits/stdc++.h>
using namespace std;
const int N=114514;
int n; 
int l[N],r[N],val[N],rnd[N],size[N],w[N];
int sz,ans,rt; 
void pushup(int x){
	size[x]=size[l[x]]+size[r[x]]+w[x];
}
void leftr(int &k){
	int t=r[k];
	r[k]=l[t];
	l[t]=k;
	size[t]=size[k];
	pushup(k);
	k=t;
}
void rightr(int &k){
	int t=l[k];
	l[t]=r[k];
	r[t]=k;
	size[t]=size[k];
	pushup(k);
	k=t;
}
void insert(int &k,int x){
	if(!k){
		sz++;k=sz;size[k]=1;
		w[k]=1;rnd[k]=rand();val[k]=x;
		return; 
	}
	size[k]++;
	if(val[k]==x)w[k]++;
	else if(val[k]<x){
		insert(r[k],x);
		if(rnd[r[k]<rnd[k]])leftr(k);
	}else{
		insert(l[k],x);
		if(rnd[k]<rnd[l[k]])rightr(k);
	}
}
bool del(int &k,int x){
	if(!k) return false;
	if(val[k]==x){
		if(w[k]>1){
			w[k]--;size[k]--;
			return true;
		}
		if(l[k]==0||r[k]==0){
			k=l[k]+r[k];
			return true;
		}else if(rnd[l[k]]<rnd[r[k]]){
        	rightr(k);
        	return del(k,x);
      	}else{
        	leftr(k);
        	return del(k,x);
        }
	}else if(val[k] < x){
      bool suc=del(r[k],x);
      if (suc)size[k]--;
      return suc;
    }else{
    	bool succ=del(l[k],x);
   		if(succ)size[k]--;
    	return succ;
	}
}
int rank(int k,int x){
	if(!k) return 0;
	if(val[k]==x){
		return size[l[k]]+1;
	}else if(val[k]<x){
		return size[l[k]]+w[k]+rank(r[k],x);
	}else return rank(l[k],x);
}
int sum(int k,int x){
	if(!k) return 0;
	if(x<=size[l[k]]) return sum(l[k],x);
	else if(x>size[l[k]]+w[k]) return sum(r[k],x-size[l[k]]-w[k]);
	else return val[k];
}
void pre(int k,int x){
    if(!k)return;
    if(val[k]<x)ans=k,pre(r[k],x);
    else pre(l[k],x);
}
void sub(int k,int x){
    if(!k) return;
    if(val[k]>x)ans=k,sub(l[k],x);
    else sub(r[k], x);
}
int main(){
	srand(114514);
	cin>>n;
	int opt,x;
	while(n--){
		cin>>opt>>x;
		if(opt==1) insert(rt,x);
		if(opt==2) del(rt,x);
		if(opt==3) printf("%d\n",rank(rt,x));
		if(opt==4) printf("%d\n",sum(rt,x));
		if(opt==5){ans=0;pre(rt,x);printf("%d\n",val[ans]);}
		if(opt==6){ans=0;sub(rt,x);printf("%d\n",val[ans]);}
	}
}