Splay模板 1.0

 struct Splay{

     int rt,sz;     ///根节点,树节点总数

     int va[N],son[N][],fa[N];///值,左右儿子,父亲

     void spin(int t){     ///旋转操作

         int x=fa[t], f=fa[x], y=son[x][]==t;

         son[x][y]=son[t][y^], fa[son[x][y]]=x;

         son[t][y^]=x, fa[x]=t, fa[t]=f;

         if(f) son[f][son[f][]==x]=t;

     }

     void play(int x){     /// splay操作

         for(int i;i=fa[x];spin(x))

             if(fa[i])

             spin((x==son[i][])==(i==son[fa[i]][])?i:x);

         rt=x;

     }

     void ins(int v){///插入元素

         int y,x=rt;

         while(){

             y=son[x][va[x]<v];

             if(!y){

                 y=++sz, va[y]=v, fa[y]=x;

                 son[y][]=son[y][]=;

                 son[x][va[x]<v]=y;

                 break;

             }

             x=y;

         }play(y);

     }

     int suc(){    ///找后继

         int x=rt,y=son[x][];

         while(son[y][])y=son[y][];

         return va[y];

     }

     int pre(){    ///找前驱

         int x=rt,y=son[x][];

         while(son[y][])y=son[y][];

         return va[y];

     }

     void init(int x){  ///初始化,需要初始值

         sz=rt=;va[rt]=x;

         fa[]=son[][]=son[][]=;

     }

 }splay;