#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
int root=1,ftsize=0;
struct ftreap
{
int ls,rs,size,v,w;
} ft[100005];
void update(int t)
{
ft[t].size=ft[ft[t].ls].size+ft[ft[t].rs].size+1;
}
int newdata(int x)
{
int id=++ftsize;
ft[id].size=1;
ft[id].v=x;
ft[id].w=rand();
return id;
}
void split(int t,int val,int &x,int &y)
{
if(!t)
{
x=y=0;
return;
}
if (ft[t].v<=val)
{
x=t;
split(ft[t].rs,val,ft[t].rs,y);
}
else
{
y=t;
split(ft[t].ls,val,x,ft[t].ls);
}
update(t);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(ft[x].w<ft[y].w)
{
ft[y].ls=merge(x,ft[y].ls);
update(y);
return y;
} else
{
ft[x].rs=merge(ft[x].rs,y);
update(x);
return x;
}
}
void insert(int x)
{
int i,j;
split(root,x,i,j);
root=merge(i,merge(newdata(x),j));
}
void del(int x)
{
int i,j,k,l,m;
split(root,x,i,j);
split(i,x-1,k,l);
m=merge(ft[l].ls,ft[l].rs);
root=merge(merge(k,m),j);
}
int get_rank(int x)
{
int i,j,res;
split(root,x-1,i,j);
res=ft[i].size+1;
root=merge(i,j);
return res;
}
int kth(int t,int k)
{
if(k==ft[ft[t].ls].size+1) return t;
if(k<=ft[ft[t].ls].size) return kth(ft[t].ls,t);
else return kth(ft[t].rs,t-ft[ft[t].ls].size-1);
}
int pre(int x)
{
int i,j;
split(root,x-1,i,j);
int res=ft[kth(i,ft[i].size)].v;
root=merge(i,j);
return res;
}
int next(int x)
{
int i,j;
split(root,x,i,j);
int res=ft[kth(j,1)].v;
root=merge(i,j);
return res;
}
int main()
{
srand(time(NULL));
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int opt,x;
cin>>opt>>x;
switch (opt)
{
case 1:
insert(x);
break;
case 2:
del(x);
break;
case 3:
cout<<get_rank(x)<<endl;
break;
case 4:
cout<<ft[kth(root,x)].v<<endl;
break;
case 5:
cout<<pre(x)<<endl;
break;
case 6:
cout<<next(x)<<endl;
break;
}
}
return 0;
}
为什么会MLE