背景
最近在学平衡树，学了一下Splay，自己打了一些注释，现在放到这里
题目
3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 26996 Solved: 12493
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
代码
贴一份便于自己理解的Splay代码（蒯代码可耻）
#include <bits/stdc++.h>
#define N (100000+5)
using namespace std;
int fa[N],ch[N][2],val[N],cnt[N],siz[N],rt,tot;
void maintain(int x){//改变节点位置后，更新size
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];//左+右+自身大小
}
bool get(int x){//判断x是fa[x]的左儿子(0),还是右儿子(1)
return x==ch[fa[x]][1];
}
void clear(int x){//销毁节点x
ch[x][0]=ch[x][1]=fa[x]=val[x]=siz[x]=cnt[x]=0;
}
void rotate(int x){
int y=fa[x],z=fa[y],k=get(x);//y:x的父亲，z:x的爷爷，k:x是y的哪个儿子
ch[y][k]=ch[x][k^1];//y的那个儿子设置成x的另一个儿子
fa[ch[x][k^1]]=y;//和上语句是一组
ch[x][k^1]=y;//x的另一个儿子设置成y
fa[y]=x;//和上语句是一组
fa[x]=z;//x的父亲设为z
if(z) ch[z][y==ch[z][1]]=x;//y原来的那个位置设为x
maintain(y),maintain(x);//更新节点大小
}
void splay(int x,int g=0){//Splay操作
while(fa[x]!=g){//如果父亲不是目标节点，就旋转
int f=fa[x],ff=fa[f];//父亲，祖父
if(ff!=g) get(x)==get(f)?rotate(f):rotate(x);//如果在同一边，则转父亲，不在同一边，转自己
rotate(x);//再转一次自己
}
if(!g)rt=x;
}
void insert(int k){//插入操作
if(!rt){//如果没有根节点
val[++tot]=k;//tot++，tot的val为k
cnt[tot]++;//tot的cnt++
rt=tot;//根节点是tot
maintain(rt);//更新rt
return;
}//不然的话
int cnr=rt,f=0;//设当前节点(cnr)为rt，当前节点的父亲(f)为0
while(1){
if(val[cnr]==k){//如果当前节点的值正好是k
cnt[cnr]++;//当前节点cnt++
maintain(cnr);//更新cnr
maintain(f);//更新其father(f)
splay(cnr);//Splay一下
break;//结束
}
//跳到下一个节点
f=cnr;//父亲变成当前的这个
cnr=ch[cnr][val[cnr]<k];//当前的这个变成其儿子
if(!cnr){//如果当前节点是空的话
val[++tot]=k;//tot++，val为k
cnt[tot]++;//cnt++
fa[tot]=f;//father为f
ch[f][val[f]<k]=tot;//father的这个儿子为tot
maintain(tot);//更新tot
maintain(f);//更新f
splay(tot);//Splay一下
break;//结束
}
}
}
/*Splay基本功能****************************************************/
int rk(int k){//查询x的排名
int res=0,cnr=rt;//res为排名，cnr当前节点
while(1){
if(k<val[cnr]){//在树左边
cnr=ch[cnr][0];//当前节点为左儿子
}
else{//在树右边或自己
res+=siz[ch[cnr][0]];//加左子树的所有siz
if(k==val[cnr]){//正好是自己
splay(cnr);
return res+1;//返回res+1
}
res+=cnt[cnr];//不是自己，加上cnt
cnr=ch[cnr][1];//向右边查询
}
}
}
int kth(int k){//查询k大的数（k为剩余排名）
int cnr=rt;//初始节点为根
while(1){
if(ch[cnr][0]&&k<=siz[ch[cnr][0]]) cnr=ch[cnr][0];
//左子树有值且k比左子树大小要小（或等） 当前节点跳至左子树
else{
k-=cnt[cnr]+siz[ch[cnr][0]];//k-左子树大小
if(k<=0) return val[cnr];//k<=0 该节点为所求
cnr=ch[cnr][1];//跳至右儿子
}
}
}
int pre(){//查询前驱
int cnr=ch[rt][0];
while(ch[cnr][1]) cnr=ch[cnr][1];
return cnr;
}
int nxt(){//查询后继
int cnr=ch[rt][1];
while(ch[cnr][0]) cnr=ch[cnr][0];
return cnr;
}
int del(int k){//删除操作
rk(k);
if(cnt[rt]>1){
cnr[rt]--;
maintain(rt);
return;
}
if(!ch[rt][0]&&!ch[rt][1]){
clear(rt);
rt=0;
return;
}
if(!ch[rt][0]){
int cnr=rt;
rt=ch[rt][1];
fa[rt]=0;
clear(cnr);
return;
}
if(!ch[rt][1]){
int cnr=rt;
rt=ch[rt][1];
fa[rt]=0;
clear(cnr);
return;
}
int x=pre(),cnr=rt;
splay(x);
fa[ch[cnr][1]]=x;
ch[x][1]=ch[cnr][1];
clear(cnr);
maintain(rt);
}
int main(){
return 0;
}