treap版见【这里】。
splay版见【这里】。
替罪羊树。
#include<cstdio>
#include<algorithm>
using namespace std;
const double r=0.78;
const int maxn=100010,oo=0x3f3f3f3f;
int rd()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9'){if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int son[maxn][2],siz[maxn],num[maxn],w[maxn],cnt[maxn],
fid[maxn],fw[maxn],fcnt[maxn],sta[maxn],
tot,clo,rt,id,fa,b;
void pause()
{int x;x=1;
}
void upd(int u)
{if (!u) return;siz[u]=siz[son[u][0]]+siz[son[u][1]]+1;num[u]=num[son[u][0]]+num[son[u][1]]+cnt[u];
}
void check(int u)
{if (!u) return;if (siz[son[u][0]]>siz[u]*r||siz[son[u][1]]>siz[u]*r)id=u,fa=-1;if (son[u][0]==id){fa=u;b=0;}if (son[u][1]==id){fa=u;b=1;}
}
void dfs(int u)
{if (!u) return;dfs(son[u][0]);clo++;fid[clo]=u;fw[clo]=w[u];fcnt[clo]=cnt[u];dfs(son[u][1]);
}
int build(int L,int R)
{if (L>R) return 0;int mid=L+R>>1,u;u=fid[mid];w[u]=fw[mid];cnt[u]=fcnt[mid];son[u][0]=build(L,mid-1);son[u][1]=build(mid+1,R);upd(u);return u;
}
int solve(int u)
{/*if (siz[son[u][0]]==-1) pause();printf("%d:%dvs%d\n",siz[u],siz[son[u][0]],siz[son[u][1]]);*/clo=0;dfs(u);return build(1,clo);
}
int ins(int u,int x)
{if (!u){u=++tot;w[u]=x;cnt[u]=siz[u]=num[u]=1;return u;}if (w[u]==x){cnt[u]++;num[u]++;return u;}son[u][x>w[u]]=ins(son[u][x>w[u]],x);upd(u);check(u);return u;
}
int del(int u,int x)
{//if (x==-8195776) pause();if (x==w[u]){cnt[u]--;if (!cnt[u]){if (son[u][0]*son[u][1]==0) u=son[u][0]+son[u][1];else{int fl=siz[son[u][0]]<siz[son[u][1]];int p=son[u][fl],top=0;while (son[p][fl^1]) sta[++top]=p,p=son[p][fl^1];if (top){son[sta[top]][fl^1]=son[p][fl];son[p][0]=son[u][0];son[p][1]=son[u][1];for (;top;top--) upd(sta[top]);}else son[p][fl^1]=son[u][fl^1];u=p;}}upd(u);check(u);return u;}son[u][x>w[u]]=del(son[u][x>w[u]],x);upd(u);check(u);return u;
}
int rank(int u,int x)
{if (!u) return 0;if (x==w[u]) return num[son[u][0]]+1;if (x<w[u]) return rank(son[u][0],x);return cnt[u]+num[son[u][0]]+rank(son[u][1],x);
}
int qry(int u,int x)
{if (x<=num[son[u][0]]) return qry(son[u][0],x);if (x<=cnt[u]+num[son[u][0]]) return w[u];return qry(son[u][1],x-(cnt[u]+num[son[u][0]]));
}
int pre(int u,int x)
{if (!u) return -oo;if (w[u]>=x) return pre(son[u][0],x);return max(w[u],pre(son[u][1],x));
}
int succ(int u,int x)
{if (!u) return oo;if (w[u]<=x) return succ(son[u][1],x);return min(w[u],succ(son[u][0],x));
}
int main()
{/*freopen("phs.in","r",stdin);freopen("phs.out","w",stdout);*/int n,opt;n=rd();while (n--){/*if (n%3000==0) printf("%d\n",n);if (n%5000==0) pause();*/opt=rd();switch (opt){case 1:id=-1;rt=ins(rt,rd());if (id>0){if (fa==-1) rt=solve(id);else son[fa][b]=solve(id);}break;case 2:id=-1;rt=del(rt,rd());if (id>0){if (fa==-1) rt=solve(id);else son[fa][b]=solve(id);}break;//default:rd();break;case 3:printf("%d\n",rank(rt,rd()));break;case 4:printf("%d\n",qry(rt,rd()));break;case 5:printf("%d\n",pre(rt,rd()));break;case 6:printf("%d\n",succ(rt,rd()));break;/*case 3:rank(rt,rd());break;case 4:qry(rt,rd());break;case 5:pre(rt,rd());break;case 6:succ(rt,rd());break;*/}}
}