只有60分
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9+7;
int n,r=0,num[1000005],siz[10000005],son[10000005][2],rd[10000005],val[10000005],tot;
void pushup(int x){
siz[x]=siz[son[x][0]]+siz[son[x][1]]+num[x];
}
void rotate(int &p,int d){
int k=son[p][d^1];
son[p][d^1]=son[k][d];
son[k][d]=p;
pushup(p);
pushup(k);
p=k;
}
void insert(int &p,int x){
if(!p){
p=++tot;
siz[p]=num[p]=1;
val[p]=x;
rd[p]=rand();
return;
}
else if(val[p]==x){
num[x]++;
siz[x]++;
return;
}
else{
int d=(x>val[p]);
insert(son[p][d],x);
if(rd[p]<rd[son[p][d]]) rotate(p,d^1);
}
pushup(p);
}
void del(int &p,int x){
if(!p) return;
if(x>val[p]) del(son[p][1],x);
else if(x<val[p]) del(son[p][0],x);
else{
if(!son[p][0]&&!son[p][1]){
num[p]--,siz[p]--;
if(!num[p]) p=0;
}
else if(son[p][0]&&!son[p][1]){
rotate(p,1);
del(son[p][1],x);
}
else if(!son[p][0]&&son[p][1]){
rotate(p,0);
del(son[p][0],x);
}
else{
int d=(rd[son[p][0]]>rd[son[p][1]]);
rotate(p,d);
del(son[p][d],x);
}
}
pushup(p);
}
int rnk(int p,int x){
if(!p) return 0;
if(val[p]==x) return siz[son[p][0]]+1;
else if(val[p]>x) return rnk(son[p][0],x);
else return rnk(son[p][1],x)+siz[son[p][0]]+num[p];
}
int kth(int p,int x){
if(!p) return 0;
if(x<=siz[son[p][0]]) return kth(son[p][0],x);
else if(x>siz[son[p][0]]+num[p]) return kth(son[p][1],x-siz[son[p][0]]-num[p]);
else return val[p];
}
int pre(int p,int x){
if(!p) return -inf;
if(x<=val[p]) return pre(son[p][0],x);
else return max(val[p],pre(son[p][1],x));
}
int lst(int p,int x){
if(!p) return inf;
if(x>=val[p]) return lst(son[p][1],x);
else return min(val[p],lst(son[p][0],x));
}
signed main(){
//freopen("a.txt","r",stdin);
//freopen("b.txt","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
int opt;
cin>>opt;
if(opt==1){
int x;
cin>>x;
insert(r,x);
}
else if(opt==2){
int x;
cin>>x;
del(r,x);
}
else if(opt==3){
int x;
cin>>x;
cout<<rnk(r,x)<<endl;
}
else if(opt==4){
int x;
cin>>x;
cout<<kth(r,x)<<endl;
}
else if(opt==5){
int x;
cin>>x;
cout<<pre(r,x)<<endl;
}
else{
int x;
cin>>x;
cout<<lst(r,x)<<endl;
}
}
return 0;
}