参考：

http://blog.csdn.net/clove_unique/article/details/50630280

gty课件

找一个好的风格太难了，自己习惯用struct，就强行用struct写了一下数组版的，同时加了些宏简化代码

都是迭代写法

splay要维护fa指向父亲

rotate是把x转到fa，要更新f和x

splay是把x转到tar的孩子，x成为root就是tar=0，注意更新root

ins考虑空树，考虑已经存在，插入新节点的话要保留last到最后处理父亲，然后做splay

(递归写法的传引用已经解决了设置祖先的问题)

del

先找要删除的，splay到根

1.多个直接--

2.空树直接root=0

3.只有一个儿子,令独生子变成根,删去该点。

4.左右儿子都有。找到左子树中权值最大的点,将其 splay 到左儿子的位置。然后将 整棵右子树挂在左儿子的右边。删除节点。 

其他操作差不多了

 

ps：比treap慢了一倍

 

////  main.cpp//  splay////  Created by Candy on 27/11/2016.//  Copyright © 2016 Candy. All rights reserved.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define pa t[x].fa#define lc t[x].ch[0]#define rc t[x].ch[1]const int N=2e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct node{    int fa,ch[2],v,w,size;}t[N];int cnt,root;inline int wh(int x){
    return t[pa].ch[1]==x;}inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;}inline void rotate(int x){
    //x-->pa    int f=t[x].fa,g=t[f].fa,c=wh(x);    if(g) t[g].ch[wh(f)]=x;    t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f;    t[x].ch[c^1]=f;t[f].fa=x;    t[x].fa=g;    update(f);update(x);}inline void splay(int x,int tar){
    //x-->x.fa==tar    for(;t[x].fa!=tar;rotate(x))        if(t[pa].fa!=tar) rotate(wh(x)==wh(pa)?pa:x);    if(tar==0) root=x;}inline int nw(int v){    cnt++;    t[cnt].v=v;t[cnt].ch[0]=t[cnt].ch[1]=t[cnt].fa=0;    t[cnt].w=t[cnt].size=1;    return cnt;}inline void ins(int v){    if(root==0){root=nw(v);return;}//empty tree    int x=root,last=0;    while(x!=0){        if(t[x].v==v){t[x].w++;t[x].size++;splay(x,0);return;}        last=x;        if(v
           
            1) {t[x].w--,t[x].size--;return;} if(lc==0&&rc==0) root=0; else if(rc==0) t[lc].fa=0,root=lc; else if(lc==0) t[rc].fa=0,root=rc; else{ int tmp=t[root].ch[0]; while(t[tmp].ch[1]) tmp=t[tmp].ch[1]; splay(tmp,x); t[tmp].ch[1]=rc;t[rc].fa=tmp; t[tmp].fa=0; root=tmp; update(root); }}inline int rnk(int v){ int x=root,ls=0; while(x!=0){ if(t[x].v==v){ int ans=ls+t[lc].size+1; splay(x,0); return ans; } if(v
           
          
         
        
       
      

 

[2016-11-30]

复习了一遍

注意：

find和ins操作要splay，有的地方直接return的话忘记splay了

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define pa t[x].fa#define lc t[x].ch[0]#define rc t[x].ch[1]const int N=2e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct node{    int fa,ch[2],w,size,v;}t[N];int cnt,root;inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;}inline int wh(int x){
   return t[pa].ch[1]==x;}inline void rotate(int x){    int f=t[x].fa,g=t[f].fa,c=wh(x);    if(g) t[g].ch[wh(f)]=x;t[x].fa=g;    t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f;    t[x].ch[c^1]=f;t[f].fa=x;    update(f);update(x);}inline void splay(int x,int tar){    for(;t[x].fa!=tar;rotate(x))        if(t[pa].fa!=tar) rotate(wh(pa)==wh(x)?pa:x);    if(tar==0) root=x;}inline int nw(int v){    cnt++;    t[cnt].ch[0]=t[cnt].ch[1]=t[cnt].fa=0;    t[cnt].w=t[cnt].size=1;t[cnt].v=v;    return cnt;}void ins(int v){    if(root==0){root=nw(v);return;}    int x=root,last=0;    while(x){        if(t[x].v==v){t[x].w++;t[x].size++;splay(x,0);return;}        last=x;        if(v
          
           1){t[x].w--;t[x].size--;return;} if(lc==0&&rc==0) root=0; else if(rc==0) t[lc].fa=0,root=lc; else if(lc==0) t[rc].fa=0,root=rc; else{ int _=lc; while(t[_].ch[1]) _=t[_].ch[1]; splay(_,x); t[_].ch[1]=rc;t[rc].fa=_; t[_].fa=0;root=_; update(root); }}int rnk(int v){ int x=root,ls=0; while(x){ if(t[x].v==v){ int ans=ls+t[lc].size+1; splay(x,0); return ans; } if(v
           
            t[x].v) ans=x,x=rc; else x=lc; } return ans;}int suf(int v){ int x=root,ans=0; while(x){ if(v