省选将至，慌得一批，hale赶紧去学了学splay，防止被打爆，虽说一定会被打爆的

不过这玩意是真的恶心，hale花了三个中午去搞掉他

一点点自己的理解啦，嘤嘤嘤

emmm，废话少说进入正题

一 。啥是平衡树？

根据百度百科上面说的：

     平衡树，即平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

嗯，说得很好，我也知道他很好啊，哼唧唧、

二。平衡树可以干什么？

  通过不断调整自身平衡来不使自身退化成链，以便于操作，比如查询前驱后继，插入一个数，删除一个数，查询排名为k的数

先解释一下变量名

 

struct node{    int ch[2];//左右儿子    int son;//儿子的总数便于查询排名    int cnt;//当前值的个数    int val;//当前节点的值    int ff;//保存父亲 } t[N];

 

操作集合如下

1。push_up操作，

其实我也不知道给他取什么名字了，比较线段树的同名操作也就不难理解了

 

void push_up(int u){    t[u].son=t[t[u].ch[0]].son+t[t[u].ch[1]].son+t[u].cnt;}

 

2。左右旋转操作，这里的话可以参见别人的博克去理解哦 主要是我真的讲不好这个东西  

但是我这个旋转码量小，可以作为参考而且也挺快的

void rotate(int x){    int y=t[x].ff;//当前x的父亲     int z=t[y].ff;//当前x的爷爷     int k=t[y].ch[1]==x;    t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;    t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;    t[x].ch[k^1]=y;t[y].ff=x;//一系列的连边操作     push_up(y);push_up(x);//向上维护信息 }void splay(int x,int goal)//当前点，目标点 {    while (t[x].ff!=goal)//还未到达目标点     {        int y=t[x].ff;        int z=t[y].ff;//同上面的rotate         if (z!=goal) (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);//判断是否在一条链上         rotate(x);    }    if (goal==0) root=x;}

三。插入一个数

void insert(int x)//插入一个x的数 {    int u=root,ff=0;//用来记录父亲     while (u&&t[u].val!=x)    {        ff=u;        u=t[u].ch[x>t[u].val];//很妙的操作，自己想想，也就不难明白为什么的用ch[2]来定义左右儿子了     }    if (u) t[u].cnt++;//如果存在就直接记录个数     else//不然就重新开点     {        u=++tot;        if (ff) t[ff].ch[x>t[ff].val]=u;        t[u].ch[1]=0;t[u].ch[0]=0;        t[u].val=x;t[u].ff=ff;        t[u].cnt=1;t[u].son=1;//开点的一些基本操作     }  splay(u,0);//将点旋上去，保持树的平衡 }

四。查找一个数

void find(int x){    int u=root;    if (!u) return;//这个数不存在，直接退出     while (t[u].ch[x>t[u].val]&&x!=t[u].val)     u=t[u].ch[x>t[u].val];//不断向下查询位置     splay(u,0);//将这个点旋上来 }

五。查询前驱后驱

int Next(int x,int f){    find(x);int u=root;//找到查询的点旋上来    if ((t[u].val>x&&f)||(t[u].val

六。删除一个数

void Delete(int x){    int last=Next(x,0);//查询这个数的前驱     int next=Next(x,1);//查询这个数的后继 以确定位置     splay(last,0);splay(next,last);//旋上去     int del=t[next].ch[0];//找到删的这个点     if (t[del].cnt>1)//若大于一，则个数减一     {        t[del].cnt--;        splay(del,0);    }    else t[next].ch[0]=0;//不然直接断掉 }

七。查询第k小数

int K_th(int x){    int u=root;    if (t[u].son
     
      t[y].son+t[u].cnt)//左儿子大于x证明要去右区间去查询         {            x-=t[y].son+t[u].cnt;            u=t[u].ch[1];        }        else if (t[y].son>=x) u=y;//不然在当前区间查询         else return t[u].val;//否则就找到啦     }}
     

好了，区间翻转的坑回头再填了，会很快的，最近作业太多了

hale要加油了，接下来放出代码

#include
     
      using namespace std;int m,n,k,p,root,cnt,tot,opt;const int N=2e6+6;struct node{    int ch[2],son,cnt,val,ff;} t[N];void push_up(int u){    t[u].son=t[t[u].ch[0]].son+t[t[u].ch[1]].son+t[u].cnt;}void rotate(int x){    int y=t[x].ff;     int z=t[y].ff;     int k=t[y].ch[1]==x;    t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;    t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;    t[x].ch[k^1]=y;t[y].ff=x;     push_up(y);push_up(x); }void splay(int x,int goal) {    while (t[x].ff!=goal)     {        int y=t[x].ff;        int z=t[y].ff;          if (z!=goal) (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);         rotate(x);    }    if (goal==0) root=x;}void insert(int x) {    int u=root,ff=0;     while (u&&t[u].val!=x)    {        ff=u;        u=t[u].ch[x>t[u].val];     }    if (u) t[u].cnt++;     else     {        u=++tot;        if (ff) t[ff].ch[x>t[ff].val]=u;        t[u].ch[1]=0;t[u].ch[0]=0;        t[u].val=x;t[u].ff=ff;        t[u].cnt=1;t[u].son=1;     }  splay(u,0); }void find(int x){    int u=root;    if (!u) return;     while (t[u].ch[x>t[u].val]&&x!=t[u].val)     u=t[u].ch[x>t[u].val];     splay(u,0); }int Next(int x,int f){    find(x);int u=root;    if ((t[u].val>x&&f)||(t[u].val
      
       1)     {        t[del].cnt--;        splay(del,0);    }    else t[next].ch[0]=0; }int K_th(int x){    int u=root;    if (t[u].son
       
        t[y].son+t[u].cnt)         {            x-=t[y].son+t[u].cnt;            u=t[u].ch[1];        }        else if (t[y].son>=x) u=y;         else return t[u].val;     }}int main(){ insert(-2146483647);  insert(+2146483647);  scanf("%d",&n);  for (int i=1;i<=n;i++)  { int x;scanf("%d%d",&opt,&x);    if (opt==1) {insert(x);}    if (opt==2) {Delete(x);}    if (opt==3) {find(x);printf("%d\n",t[t[root].ch[0]].son);}    if (opt==4) {printf("%d\n",K_th(x+1));}    if (opt==5) {printf("%d\n",t[Next(x,0)].val);}    if (opt==6) {printf("%d\n",t[Next(x,1)].val);}  }  return 0;}