1 struct Splay{ 2     int rt,sz;     ///根节点,树节点总数 3     int va[N],son[N][2],fa[N];///值,左右儿子,父亲 4     void spin(int t){     ///旋转操作 5         int x=fa[t], f=fa[x], y=son[x][1]==t; 6         son[x][y]=son[t][y^1], fa[son[x][y]]=x; 7         son[t][y^1]=x, fa[x]=t, fa[t]=f; 8         if(f) son[f][son[f][1]==x]=t; 9     }10     void play(int x){     /// splay操作11         for(int i;i=fa[x];spin(x))12             if(fa[i])13             spin((x==son[i][0])==(i==son[fa[i]][0])?i:x);14         rt=x;15     }16     void ins(int v){///插入元素17         int y,x=rt;18         while(1){19             y=son[x][va[x]<v];20             if(!y){21                 y=++sz, va[y]=v, fa[y]=x;22                 son[y][0]=son[y][1]=0;23                 son[x][va[x]<v]=y;24                 break;25             }26             x=y;27         }play(y);28     }29     int suc(){    ///找后继30         int x=rt,y=son[x][1];31         while(son[y][0])y=son[y][0];32         return va[y];33     }34     int pre(){    ///找前驱35         int x=rt,y=son[x][0];36         while(son[y][1])y=son[y][1];37         return va[y];38     }39     void init(int x){  ///初始化,需要初始值40         sz=rt=1;va[rt]=x;41         fa[1]=son[1][0]=son[1][1]=0;42     }43 }splay;