#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
struct FHQ_treap{
int tot,root;
struct node{
int ls,rs,val,siz,cnt,rnd;
}T[100010];
void FHQ(){tot=root=0;}
void updata(int x){T[x].siz=T[T[x].ls].siz+T[T[x].rs].siz+T[x].cnt;}
void split(int now,int &a,int &b,int val)
{
if(!now){a=b=0;return ;}
if(T[now].val<=val)a=now,split(T[now].rs,T[now].rs,b,val);
else b=now,split(T[now].ls,a,T[now].ls,val);
updata(now);
}
int merge(int a,int b)
{
if(!a||!b)return a|b;
if(T[a].rnd<T[b].rnd){T[a].rs=merge(T[a].rs,b),updata(a);return a;}
else{T[b].ls=merge(a,T[b].ls),updata(b);return b;}
}
int new_node(int val)
{
T[++tot].val=val,T[tot].siz=T[tot].cnt=1,T[tot].rnd=rand();
return tot;
}
void insert(int val)
{
int x,y,z;
split(root,x,y,val);
root=merge(merge(x,new_node(val)),y);
}
void erase(int val)
{
int x,y,z;
split(root,x,y,val);
split(root,y,z,val-1);
y=merge(T[y].ls,T[y].ls);
root=merge(x,z);
}
int find_val(int now,int rank)
{
while(233)
{
if(rank<=T[T[now].ls].siz)now=T[now].ls;
else if(rank==T[T[now].ls].siz+T[now].cnt)return T[now].val;
else rank=rank-T[T[now].ls].siz-T[now].cnt,now=T[now].rs;
}
}
int find_rank(int q)
{
int x,y,z;
split(root,x,y,q-1);
int ans=T[x].siz+1;
root=merge(merge(x,y),z);
return ans;
}
int find_pre(int q)
{
int x,y,z;
split(root,x,y,q-1);
int ans=find_val(x,T[x].siz);
root=merge(x,y);
return ans;
}
int find_nxt(int q)
{
int x,y,z;
split(root,x,y,q);
int ans=find_val(y,1);
root=merge(x,y);
return ans;
}
}FHQ;
int main()
{
srand(time(0));
int m;
cin>>m;
FHQ.FHQ();
while(m--)
{
int opt,x;
cin>>opt>>x;
if(opt==1) FHQ.insert(x);
else if(opt==2) FHQ.erase(x);
else if(opt==3) cout<<FHQ.find_rank(x)<<endl;
else if(opt==4) cout<<FHQ.find_val(FHQ.root,x)<<endl;
else if(opt==5) cout<<FHQ.find_pre(x)<<endl;
else if(opt==6) cout<<FHQ.find_nxt(x)<<endl;
}
}
就很不对,真的没找到惹嘤嘤嘤。
如果是手残错误轻喷嘤嘤嘤