二叉搜索树。
二叉搜索树是一棵二叉树。对于这棵树上的任意一个节点，右子树中的所有节点都大于它；左子树中的所有节点都小于它。
基于这个性质，我们可以以\(O(h)\)的时间的复杂度，来完成下述操作：
1.插入一个元素。
2.删除其中任意一个元素。
3.查找其中的一个元素。
4.查找第\(k\)大数。
5.询问某数的排名。
6.以常数更小的方式来查找一个数的前驱/后继。
7.以\(O(n)\)输出有序的整棵树。
8.查找将一个数插入树后的前驱/后继。
9.查找一个节点的子树大小。
下面我们一一讨论下述操作的实现。
操作6可能是最容易理解的一种操作。对于一个节点，如果要寻找它的后继，那么它的后继一定在如下两个位置之一：它的右子树，或者它的父亲。
如果它有右子树，那么它的后继一定在它的右子树中。这是因为，对于其他所有点，要么比它和它的右子树中的所有节点更大，要么比它们更小。这由二叉搜索树的基本性质可以轻松证明。
然后，它的后继一定是它的右子树中的最小点，这是因为右子树中的所有点都大于它。显然，这个最小点是右子树中最左的节点。我们称其为「后继右左定理」。
而上述的内容对于求一个有左子树的节点的前驱显然仍然是成立的。
如果它没有右子树，那么对于它的所有祖先，存在两种情况。
一是不存在任意一个祖先，使得这个祖先的父亲在这个祖先的右边，这种情况下，因为它没有右子树，所以它一定是整棵树中最大的节点，这样它就没有后继了；
另外一种是至少存在一个祖先，使得这个祖先的父亲在这个祖先的左边。
即，以这个祖先为根的整棵子树都是这个祖先的父亲的左子树，则此时很显然该节点是整棵子树中最右的节点。那么它显然是这个祖先的父亲的前驱。这可以根据「前驱左右定理」得出。
这样，我们就可以对任意的一个节点找到它的（如果存在）前驱和/或后继。
在有了操作6之后，我们就可以考虑操作1。如果插入的数比已有的任何数都大/都小，那么就一定可以插入到最右/左节点的右/左儿子。
如果不是这样的话，那么，它的大小一定在原来的一对大小相邻的数之间。
而综合「前驱左右定理」和「后继右左定理」，可以得出，一对大小相邻的节点之中，有且仅有一方的可以通过在子树中寻找来找到另一方。
这也就意味着，较大者的左子树和较小者的右子树中有且仅有一个是空的。那么，我们就一定可以把一个新的节点插入到一个空节点。
然后我们考虑操作3。它可以通过递归的二分操作来实现。假设我们当前在以\(x\)为根节点的子树中查找指定节点，
那么我们就可以根据二叉搜索树的性质，判断这个节点是\(x\)，或位于\(x\)的某一棵子树中。
于是我们就可以递归查找任意一个数。
同理，操作8也是可以用相似的方法来实现。当这个数递归查找到一个无法继续查找的节点\(x\)，
那么\(x\)一定是需要查找的数的前驱/后继，然后我们就可以通过操作6来查找这个数的后继/前驱。
接下来我们考虑操作4。操作4本质上也是一个树上二分的过程。我们首先计算出所有子树的大小，然后依据子树大小的单调性来递归查找第\(k\)大数。
于是我们考虑操作5，操作5可以在实现操作3的过程中实现。当每一次我们递归查找，我们同样也可以确定目标排名所在的一个区间，并且不断缩小这个区间。
事实上，每一次向下递归查找的过程，都确定了一部分的数一定大于或者小于目标数。当找到目标节点的时候，目标节点的区间就可以根据已有信息和它的左右子树（如果存在）来确定。
操作7就显得很显然了。通过中序遍历，我们可以以小-中-大的顺序来遍历整棵二叉树，也就将二叉树展开为一个有序序列。
它体现了二叉搜索树的性质的一个有趣的性质——对于任意一棵子树，它总是对应着有序序列上的一个连续区间。
这是因为，这棵子树之外的所有点，要么大于这棵子树中的所有点，要么小于这棵子树中的所有点。
另一方面，我们也可以从顶向下来理解这个过程。
对于根节点，它的左子树中的所有节点（如果存在）在序列中一定位于它左侧，而右子树（如果存在）中的所有节点在序列中一定位于它的右侧。
那么，递归地考虑每个子树，根据二叉搜索树的基本性质，它们都对应着一个有序的序列。所以它们总是对应着有序序列上的一个连续区间。
通过这种理解方式，我们也可以相应的理解（乃至证明）上诉的所有操作和性质。
下面是所有操作中最复杂的操作2，事实上操作2是唯一一个可能改变已有结构的操作。
对于需要删除的节点，存在三种情况。
情况一：它是一个叶节点。对于这种情况，我们只需要单纯地删除它，然后自底向顶更新子树大小。
情况二：它只有一个子节点。对于这种情况，我们只需要单纯地删除它，然后将它的子树接在它的父节点，然后自顶向上更新子树大小。
情况三：它既有左节点又有右节点。这种情况可能会比较复杂。首先我们知道，这个节点必然有前驱/后继。不妨将它的其他部分放在它的后继上。（前驱同理。）
这时候分两类讨论。
如果它的后继不是它的右子节点，那么可以将它的后继接在它的父节点，然后将它的右子树的其他部分作为它的后继的右子树。然后将它的左子树作为它的后继的左子树。
否则，我们将它的左节点放在它的后继的左节点处，然后将它的后继接在它的父节点。
对于操作9，我们只需要在每次更新的时候自顶向上计算贡献，存储好即可直接写出。
二叉搜索树是平衡树的基础，由于没有相关模板题，所以我也不太确定我的二叉搜索树有没有写挂。请各位多多指教。
#include<iostream>
#include<cstdio>
int st[100005],tp=0;
struct data{
int v;int fa;int ls;int rs;int sz;int cnt;
}tr[100005];
int rot=0,trt=0;
inline int nwlc(){
return tp?st[tp--]:++trt;
}
inline void init(int X){
tr[X].cnt=tr[X].fa=tr[X].ls=tr[X].rs=tr[X].sz=tr[X].v=0;
st[++tp]=X;
}
inline void rnw(int X){
int P=X;
while(P){
tr[P].sz=tr[tr[P].ls].sz+tr[tr[P].rs].sz+tr[P].cnt;
P=tr[P].fa;
}
}
inline int nwpt(int V,int FA,int LS,int RS,int SZ){
if(!rot){
int P=1;trt=1;tp=0;rot=1;
tr[P]=(data){V,0,0,0,1,1};
return P;
}
int P=nwlc();
tr[FA].v>V?tr[FA].ls=P:tr[FA].rs=P;
tr[P]=(data){V,FA,LS,RS,SZ,1};
return P;
}
inline int fndNm(int X){
int P=rot,FP=0;
while(P){
FP=P;
if(tr[P].v==X){
FP=P;
break;
}
P=X<tr[P].v?tr[P].ls:tr[P].rs;
}
return FP;
}
inline int fndMx(int X){
int P=X,FP;
while(P){
FP=P;
P=tr[P].rs;
}
return FP;
}
inline int fndMn(int X){
int P=X,FP;
while(P){
FP=P;
P=tr[P].ls;
}
return FP;
}
inline int fndPre(int X){
if(tr[X].ls){
return fndMx(tr[X].ls);
}else{
int P=X,NP;
while(P){
NP=P;
P=tr[P].fa;
if(tr[P].rs==NP){
break;
}
}
return P;
}
}
inline int fndNxt(int X){
if(tr[X].rs){
return fndMn(tr[X].rs);
}else{
int P=X,NP;
while(P){
NP=P;
P=tr[P].fa;
if(tr[P].ls==NP){
break;
}
}
return P;
}
}
inline int fndPP(int X){
int MX=fndMx(rot);
if(X<tr[MX].v){
return MX;
}
int P=rot,FP=0;
while(P){
FP=P;
if(tr[P].v==X){
FP=P;
break;
}else{
if(tr[P].v>X&&tr[tr[P].ls].v<X){
FP=P;
break;
}else if(tr[P].v<X&&tr[tr[P].rs].v>X){
FP=tr[P].rs;
break;
}
}
P=X<tr[P].v?tr[P].ls:tr[P].rs;
}
return fndPre(FP);
}
inline int fndNN(int X){
int MN=fndMn(rot);
if(X<tr[MN].v){
return MN;
}
int P=rot,FP=0;
while(P){
FP=P;
if(tr[P].v==X){
FP=P;
break;
}else{
if(tr[P].v>X&&tr[tr[P].ls].v<X){
FP=tr[P].ls;
break;
}else if(tr[P].v<X&&tr[tr[P].rs].v>X){
FP=P;
break;
}
}
P=X<tr[P].v?tr[P].ls:tr[P].rs;
}
return fndNxt(FP);
}
inline void trIns(int X){
int P=rot,FP;
while(P){
FP=P;
if(tr[P].v==X){
++tr[P].cnt;
rnw(P);
return;
}
P=(tr[P].v>X)?tr[P].ls:tr[P].rs;
}
rnw(nwpt(X,FP,0,0,1));
}
inline void cnnctP(int FA,int X,int SN){
if(!SN){
return;
}
tr[SN].fa=FA;
tr[FA].ls==X?(tr[FA].ls=SN):(tr[FA].rs=SN);
}
inline void delP(int FA,int X,int SN){
(tr[X].cnt>1)?--tr[X].cnt,cnnctP(FA,X,SN):cnnctP(FA,X,SN),init(X);
rnw(SN?SN:FA);
}
inline void trDel(int X){
if(!tr[X].ls&&!tr[X].rs){
delP(tr[X].fa,X,0);
}else if(tr[X].ls&&!tr[X].rs){
delP(tr[X].fa,X,tr[X].ls);
}else if(tr[X].rs&&!tr[X].ls){
delP(tr[X].fa,X,tr[X].rs);
}else{
if(tr[X].rs==fndNxt(X)){
tr[tr[X].ls].fa=tr[X].rs;
tr[tr[X].rs].ls=tr[X].ls;
delP(tr[X].fa,X,tr[X].rs);
}else{
int XN=fndNxt(X),LW;
LW=tr[XN].fa;
cnnctP(tr[XN].fa,XN,tr[XN].rs);
tr[XN].rs=tr[X].rs;
tr[tr[X].rs].fa=XN;
tr[XN].ls=tr[X].ls;
tr[tr[X].ls].fa=XN;
tr[X].rs=XN;
tr[XN].fa=X;
delP(tr[X].fa,X,XN);
rnw(LW);
}
}
}
inline int fndRnkN(int X){
int P=rot;
while(P){
if(X<=tr[tr[P].ls].sz){
X-=tr[tr[P].ls].sz;
P=tr[P].ls;
}else if(X<=tr[tr[P].ls].sz+tr[P].sz){
return P;
}else{
X-=(tr[tr[P].ls].sz+tr[P].cnt);
P=tr[P].rs;
}
}
return -1;
}
inline int fndRnkS(int X){
int P=rot,RT=0;
while(P){
P=(X<tr[P].v)?tr[P].ls:tr[P].rs,RT+=tr[tr[P].ls].sz;
}
return RT;
}
inline void trPrnt(int X){
if(tr[X].ls){
trPrnt(tr[X].ls);
}
printf("%d ",tr[X].v);
if(tr[X].rs){
trPrnt(tr[X].rs);
}
}
int q;
void init(){
scanf("%d",&q);
int op,x;
for(int i=1;i<=q;++i){
scanf("%d%d",&op,&x);
switch(op){
case 1: {
trIns(x);
break;
}
case 2: {
trDel(fndNm(x));
break;
}
case 3: {
printf("%d\n",fndRnkS(x));
break;
}
case 4:{
printf("%d\n",tr[fndRnkN(x)].v);
break;
}
case 5: {
printf("%d\n",tr[fndPP(x)].v);
break;
}
case 6: {
printf("%d\n",tr[fndNN(x)].v);
break;
}
}
}
}
int main(){
init();
return 0;
}