一个板子。
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100001
struct Data
{
int v,p;
}t[N];
bool cmp(const Data &a,const Data &b)
{
return a.v<b.v;
}
int T[N<<2],op[N],a[N],n,ma[N],e;
void Update(int p,int v,int rt,int l,int r)//插入删除
{
T[rt]+=v;
if(l==r) return;
int m=(l+r>>1);
if(p<=m) Update(p,v,rt<<1,l,m);
else Update(p,v,rt<<1|1,m+1,r);
}
int Kth(int K,int rt,int l,int r)//K小值
{
if(l==r) return l;
int m=(l+r>>1);
if(T[rt<<1]>=K) return Kth(K,rt<<1,l,m);
return Kth(K-T[rt<<1],rt<<1|1,m+1,r);
}
int Rank(int p,int rt,int l,int r)//排名
{
if(r<p) return T[rt];
int m=(l+r>>1),res=0;
res+=Rank(p,rt<<1,l,m);
if(m<p-1) res+=Rank(p,rt<<1|1,m+1,r);
return res;
}
int Findp(int rt,int l,int r)
{
if(l==r) return l;
int m=(l+r>>1);
if(T[rt<<1|1]) return Findp(rt<<1|1,m+1,r);
return Findp(rt<<1,l,m);
}
int Pre(int p,int rt,int l,int r)
{
if(r<p)
{
if(T[rt]) return Findp(rt,l,r);
return 0;
}
int m=(l+r>>1),Re;
if(m<p-1 && T[rt<<1|1] && (Re=Pre(p,rt<<1|1,m+1,r))) return Re;
return Pre(p,rt<<1,l,m);
}
int Findn(int rt,int l,int r)
{
if(l==r) return l;
int m=(l+r>>1);
if(T[rt<<1]) return Findn(rt<<1,l,m);
return Findn(rt<<1|1,m+1,r);
}
int Nex(int p,int rt,int l,int r)
{
if(p<l)
{
if(T[rt]) return Findn(rt,l,r);
return 0;
}
int m=(l+r>>1),Re;
if(p<m && T[rt<<1] && (Re=Nex(p,rt<<1,l,m))) return Re;
return Nex(p,rt<<1|1,m+1,r);
}
int main()
{
// freopen("bzoj3224.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&op[i],&t[i].v);
t[i].p=i;
}
sort(t+1,t+1+n,cmp);
ma[a[t[1].p]=++e]=t[1].v;
for(int i=2;i<=n;i++)
{
if(t[i].v!=t[i-1].v) ++e;
ma[a[t[i].p]=e]=t[i].v;
}
for(int i=1;i<=n;i++)
{
if(op[i]==1) Update(a[i],1,1,1,e);
else if(op[i]==2) Update(a[i],-1,1,1,e);
else if(op[i]==3) printf("%d\n",Rank(a[i],1,1,e)+1);
else if(op[i]==4) printf("%d\n",ma[Kth(ma[a[i]],1,1,e)]);
else if(op[i]==5) printf("%d\n",ma[Pre(a[i],1,1,e)]);
else printf("%d\n",ma[Nex(a[i],1,1,e)]);
}
return 0;