知识点 模板 数据结构

Splay (平衡树) 函数速查

#include<iostream>
using namespace std;
#define INf INF
const int N=1e5,INF=0x3f3f3f3f;
struct node{
    int fa;
    int son[2];
    int val,num,si;
    #define root t[0].son[1]
}t[N];
int n,cnt;
inline int ident(int x){
    if(t[t[x].fa].son[0]==x) return 0;
    else return 1;
}
inline void update(int x){
    t[x].si=t[t[x].son[0]].si+t[t[x].son[1]].si+t[x].num;
}
inline void connect(int x,int fa,int who){
    t[fa].son[who]=x;
    t[x].fa=fa;
}
inline void rotate(int x){
    int y=t[x].fa,r=t[y].fa;
    int yson=ident(x),rson=ident(y);
    connect(t[x].son[yson^1],y,yson);
    connect(y,x,yson^1);
    connect(x,r,rson);
    update(y);update(x);
}
inline void splay(int x,int to){
    to=t[to].fa;
    while(t[x].fa!=to){
        int y=t[x].fa;
        if(t[y].fa==to)rotate(x);
        else if(ident(x)==ident(y)) rotate(y),rotate(x);
        else rotate(x),rotate(x);
    }
}
inline int newnode(int v,int f){
    t[++cnt].fa=f;
    t[cnt].num=t[cnt].si=1;
    t[cnt].val=v;
    return cnt;
}
inline void insert(int x){
    int now=root;
    if(root==0){
        newnode(x,0);
        root=cnt;
    }else{
        while(1){
            t[now].si++;
            if(t[now].val==x){
                t[now].num++;
                splay(now,root);
                return ;
            }
            int nxt=x<t[now].val?0:1;
            if(!t[now].son[nxt]){
                int p=newnode(x,now);
                t[now].son[nxt]=p;
                splay(p,root);
                return ;
            }
            now=t[now].son[nxt];
        }
    }
}
inline int find(int x){
    int now=root;
    while(1){
        if(!now) return 0;
        if(t[now].val==x){
            splay(now,root);
            return now;
        }
        int nxt=x<t[now].val?0:1;
        now=t[now].son[nxt];
    }
}
inline void delet(int x){
    int pos=find(x);
    if(!pos) return ;
    if(t[pos].num>1){
        t[pos].num--;t[pos].si--;
        return ;
    }else {
        if(!t[pos].son[0]&&!t[pos].son[1]){
            root=0;
            return ;
        }else if(!t[pos].son[0]){
            root=t[pos].son[1];
            t[root].fa=0;
            return ;
        }else{
            int l=t[pos].son[0];
            while(t[l].son[1]) l=t[l].son[1];
            splay(l,t[pos].son[0]);
            connect(t[pos].son[1],l,1);
            connect(l,0,1);
            update(l);
        }
    }
}
inline int Rank(int x){
    return t[t[find(x)].son[0]].si+1;
}
inline int arank(int x){
    int now=root;
    while(1){
        int tem_num=t[now].si-t[t[now].son[1]].si;
        if(t[t[now].son[0]].si<x&&x<=tem_num){
            splay(now,root);
            return t[now].val;
        }
        if(x<tem_num) now=t[now].son[0];
        else now=t[now].son[1],x-=tem_num;
    }
}
inline int lower(int x){
    int now=root,ans=-INF;
    while(now){
        if(t[now].val<x) ans=max(ans,t[now].val);
        int nxt=x<=t[now].val?0:1;
        now=t[now].son[nxt];
    }
    return ans;
}
inline int upper(int x){
    int now=root,ans=INF;
    while(now){
        if(t[now].val>x) ans=min(ans,t[now].val);
        int nxt=x<t[now].val?0:1;
        now=t[now].son[nxt];
    }
    return ans;
}
int main()
{
    cin>>n;
    while(n--){
        int ops,x;
        scanf("%d%d",&ops,&x);
        if(ops==1) insert(x);
        else if(ops==2) delet(x);
        else if(ops==3) printf("%d\n",Rank(x));
        else if(ops==4) printf("%d\n",arank(x));
        else if(ops==5) printf("%d\n",lower(x));
        else printf("%d\n",upper(x));
    }
}//我不理解！！！