题解：
替罪羊树的模板和splay差距还是比较大的。。
按照我的splay的写法 真是都是问题。。
替罪羊树就是暴力的搞
当某颗子树大小大于这棵树的alpha时 就退出
另外删除的时候打懒标记删除
当有用个数少于alpha*n的时候，就重构
注意点：
1.找rank的时候要找比它小的个数，不能像splay那样取min
2.删除的时候要删排名为这个的，不能删这个数
以上两点的原因是
不能保证相同元素一定在左子树内，因为重构可能造成在右子树
另外找pre和scc也就不能和splay一样了
rank(x) 找的是编号最小的那个
rank(x)-1就是前驱
rank(x+1) 就是后继
替罪羊树不支持区间操作
应该写它的用处就是用来搞毒瘤树套树的。。
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define mid ((h+t)>>1)
const double alpha=0.75;
const int INF=2e9+;
const int N=4e6+;
int s[N],n,m,top,rt,t1;
struct phs{
int ls[N],rs[N],siz[N],travel[N],cnt[N],v[N];
bool f[N];
void dfs(int x)
{
if (!x) return;
dfs(ls[x]);
if (f[x]) travel[++t1]=x;
else s[++top]=x;
dfs(rs[x]);
}
void build(int &x,int h,int t)
{
x=travel[mid];
if (h==t)
{
siz[x]=cnt[x]=;
ls[x]=rs[x]=;
return;
}
if (h<mid) build(ls[x],h,mid-); else ls[x]=;
build(rs[x],mid+,t);
siz[x]=siz[ls[x]]+siz[rs[x]]+;
cnt[x]=cnt[ls[x]]+cnt[rs[x]]+;
}
void rebuild(int &x)
{
t1=; dfs(x);
if (t1) build(x,,t1);
else x=;
}
void insert(int &x,int k)
{
if (!x)
{
x=s[top--]; v[x]=k;
siz[x]=cnt[x]=f[x]=;
ls[x]=rs[x]=;
return;
}
siz[x]++; cnt[x]++;
if (k<=v[x]) insert(ls[x],k);
else insert(rs[x],k);
if ((double)max(siz[ls[x]],siz[rs[x]])>(double)siz[x]*alpha)
{
rebuild(x);
}
}
void del(int x,int k)
{
siz[x]--;
if (f[x]&&k==v[x])
{
f[x]=; return;
}
if (k<=v[x]) del(ls[x],k);
else del(rs[x],k);
}
void del(int k)
{
int now=rt;
while (now)
{
siz[now]--;
if (f[now]&&k==siz[ls[now]]+)
{
f[now]=;
return;
}
if (k<=siz[ls[now]]) now=ls[now];
else k-=siz[ls[now]]+f[now],now=rs[now];
}
}
void delete2(int x)
{
del(x);
if ((double)siz[rt]<(double) alpha*cnt[rt]) rebuild(rt);
}
int rank(int x)
{
int now=rt,ans=;
while (now)
{
if (v[now]>=x) now=ls[now];
else ans+=siz[ls[now]]+f[now],now=rs[now];
}
return(ans);
}
int get_kth(int x)
{
int now=rt;
while (now)
{
if (f[now]&&x==siz[ls[now]]+) return(v[now]);
if (siz[ls[now]]>=x) now=ls[now];
else x-=siz[ls[now]]+f[now],now=rs[now];
}
}
}S;
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
dep(i,,) s[++top]=i;
rep(i,,n)
{
// cout<<i<<endl;
int kk,x;
cin>>kk>>x;
if (kk==)
{
S.insert(rt,x);
}
if (kk==)
{
S.delete2(S.rank(x));
}
if (kk==)
{
cout<<S.rank(x)<<endl;
}
if (kk==)
{
cout<<S.get_kth(x)<<endl;
}
if (kk==)
{
cout<<S.get_kth(S.rank(x)-)<<endl;
}
if (kk==)
{
cout<<S.get_kth(S.rank(x+))<<endl;
}
}
return ;
}
https://zhuanlan.zhihu.com/p/21263304