冬令营被平衡树坑了之后，打算苦练一番数据结构（QAQ）。
先是打了一下想学好久的替罪羊树。
替罪羊树实现方法很简单，就是在不满足平衡条件的时候暴力重构子树。
调试小结：
1.删除操作分两类情况：如果某点只有一个孩子，将它的孩子提上来即可，否则将它变为它的前驱，再删去它的前驱。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double a=0.75;
inline int getnum()
{
int ans=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh*=-;ch=getchar();}
while(ch>=''&&ch<='')ans=ans*+ch-'',ch=getchar();
return fh*ans;
}
struct node{int s[],f,size,num;}t[];int tnum,root;
inline void init()
{
tnum=;root=;
t[].num=-;t[].size=;t[].s[]=;
t[].num=;t[].size=;t[].f=;
}
inline bool balance(int po)
{
return (double)t[po].size*a>=(double)t[t[po].s[]].size
&&(double)t[po].size*a>=(double)t[t[po].s[]].size;
}
int E[],esize;
void travel(int po)
{
if(t[po].s[])travel(t[po].s[]);
E[++esize]=po;
if(t[po].s[])travel(t[po].s[]);
}
int build(int l,int r)
{
if(l>r)return ;
int mid=(l+r)/,po=E[mid];
t[t[po].s[]=build(l,mid-)].f=po;
t[t[po].s[]=build(mid+,r)].f=po;
t[po].size=t[t[po].s[]].size+t[t[po].s[]].size+;
return po;
}
inline void rebuild(int po)
{
esize=;travel(po);
int fa=t[po].f,ws=(t[t[po].f].s[]==po);
int npo=build(,esize);
t[t[fa].s[ws]=npo].f=fa;
if(po==root)root=npo;
}
inline void insert(int num)
{
int now=root,npo=++tnum;
t[npo].size=;t[npo].num=num;
while(true)
{
t[now].size++;
bool ws=(num>=t[now].num);
if(t[now].s[ws])now=t[now].s[ws];
else {t[t[now].s[ws]=npo].f=now;break ;}
}
int inv=;
for(int i=npo;i;i=t[i].f)if(!balance(i))inv=i;
if(inv)rebuild(inv);
}
inline int rank(int num)
{
int now=root,ans=;
while(now)
{
if(t[now].num<num)ans+=t[t[now].s[]].size+,now=t[now].s[];
else now=t[now].s[];
}
return ans;
}
inline int getkth(int kth)
{
int now=root;
while(true)
{
if(t[t[now].s[]].size==kth-)return now;
else if(t[t[now].s[]].size>=kth)now=t[now].s[];
else kth-=t[t[now].s[]].size+,now=t[now].s[];
}
return now;
}
inline int getn(int num)
{
int now=root;
while(true)
{
if(t[now].num==num)return now;
else now=t[now].s[t[now].num<num];
}
}
inline void erase(int po)
{
if(t[po].s[]&&t[po].s[])
{
int tpo=t[po].s[];
while(t[tpo].s[])tpo=t[tpo].s[];
t[po].num=t[tpo].num;
po=tpo;
}
int son=(t[po].s[])?t[po].s[]:t[po].s[],ws=(t[t[po].f].s[]==po);
t[t[t[po].f].s[ws]=son].f=t[po].f;
for(int i=t[po].f;i;i=t[i].f)t[i].size--;
if(po==root)root=son;
}
inline int succ(int num)
{
int now=root,ans=;
while(now)
{
if(t[now].num>num)ans=min(ans,t[now].num),now=t[now].s[];
else now=t[now].s[];
}
return ans;
}
inline int pred(int num)
{
int now=root,ans=-;
while(now)
{
if(t[now].num<num)ans=max(ans,t[now].num),now=t[now].s[];
else now=t[now].s[];
}
return ans;
}
int main(int argc, char *argv[])
{
init();
int n=getnum();
for(int i=;i<=n;i++)
{
int p=getnum(),num=getnum();
if(p==)insert(num);
if(p==)erase(getn(num));
if(p==)printf("%d\n",rank(num));
if(p==)printf("%d\n",t[getkth(num+)].num);
if(p==)printf("%d\n",pred(num));
if(p==)printf("%d\n",succ(num));
}
return ;
}