删除一个点

\(near(u,c)\)求出点\(u\)的前驱和后继(即小于它的数中最大的和大于它的数中最小的,\(c=0\):前驱;\(c=1\):后继).
\(splay\)前驱,\(splay\)后继,后继变为根节点,前驱变为根节点的左儿子,\(u\)变为前驱的右子树,删去即可.

inline int near(int u,int c){
    if(tr[u].c[c]){
        u=tr[u].c[c];c^=1;
        while(tr[u].c[c])
            u=tr[u].c[c];
        return u;
    }
    while(son(u)==c){
        if(u==rt) return 0;
        u=tr[u].f;
    }
    return tr[u].f;
}
inline void clear(int u){
    tr[tr[u].f].c[son(u)]=0;
    recnt(tr[u].f);
    tr[u].c[0]=tr[u].c[1]=tr[u].f=tr[u].siz=tr[u].cnt=tr[u].val=0;
}
inline void del(int u){
    int lst=near(u,0),nxt=near(u,1);
    if(!lst||!nxt){
        splay(u);
        if(lst){
            rt=tr[u].c[0];
            tr[tr[u].c[0]].f=0;
        }
        else{
            rt=tr[u].c[1];
            tr[tr[u].c[1]].f=0;
        }
        return;
    }
    splay(lst);splay(nxt);
    rotate(lst);clear(u); 
}

数组版

\(tr[u][0]\)左儿子,\(tr[u][1]\)右儿子,\(fa[u]\)父亲,\(sz[u]\)以\(u\)为根的子树大小,\(val[u]\)为这个点表示的值,\(ct[u]\)为这个值的个数,\(rt\)为根.

int tr[N][2],fa[N],sz[N],ct[N],val[N],rt;

一些简单函数

\(son(u)\)判断\(u\)为左/右儿子.
\(recnt(u)\)重新计算以\(u\)为根的子树大小.
\(ins_p(f,u,c)\)插入\(u\),为\(f\)的\(c\)儿子.

inline bool son(int u){
    return tr[fa[u]][1]==u;
}
inline void recnt(int u){
    sz[u]=ct[u]+sz[tr[u][0]]+sz[tr[u][1]];
}
inline void ins_p(int f,int u,int c){
    fa[u]=f;tr[f][c]=u;
}

旋转

这是\(splay\)的核心代码.
以下图为例:

将紫色节点旋转到粉色节点.
将紫色节点取代粉色节点的位置;
如果紫色节点为粉色节点右儿子,紫色节点的左儿子代替紫色节点原位置,粉色节点为紫色节点左儿子;否则紫色节点的右儿子代替紫色节点原位置,粉色节点为紫色节点右儿子.
旋转后:

\(rotate(u)\)就是将\(u\)旋转到它的父亲.
\(splay(u)\)则是将\(u\)旋转到根:

• 如果\(u\)的父亲为根,直接旋转\(u\).
• 如果\(u,fa\)同为左/右儿子,先转\(fa\),再转\(u\).
• 如果\(u,fa\)不同为左/右儿子,转\(u\),再转\(u\).

inline void rotate(int u){
    int f=fa[u];bool c=son(u);
    ins_p(fa[f],u,son(f));
    ins_p(f,tr[u][c^1],c);
    ins_p(u,f,c^1);
    recnt(f);recnt(u);
    if(!fa[u]) rt=u;
}
inline void splay(int u){
    while(fa[u]){
        if(!fa[fa[u]]) rotate(u);
        else if(son(u)==son(fa[u])){
            rotate(fa[u]);rotate(u);
        }
        else{
            rotate(u);rotate(u);
        }
    }
}

插入一个值

如果存在,那个点的\(cnt+1\),否则新建一个点,把它转到根.

inline int find(int x){
    int u=rt;
    while(x!=val(u)&&u)
        if(x

inline int near(int u,int c){
    if(tr[u][c]){
        u=tr[u][c];c^=1;
        while(tr[u][c])
            u=tr[u][c];
        return u;
    }
    while(son(u)==c){
        if(u==rt) return 0;
        u=fa[u];
    }
    return fa[u];
}
inline void clear(int u){
    tr[fa[u]][son(u)]=0;recnt(fa[u]);
    tr[u][0]=tr[u][1]=fa[u]=sz[u]=ct[u]=val[u]=0;
}
inline void del(int u){
    int lst=near(u,0),nxt=near(u,1);
    if(!lst||!nxt){
        splay(u);
        if(lst){
            rt=tr[u][0];fa[tr[u][0]]=0;
        }
        else{
            rt=tr[u][1];fa[tr[u][1]]=0;
        }
        return;
    }
    splay(lst);splay(nxt);
    rotate(lst);clear(u); 
}