splaytree的板子

shadowice1984 · 2018-04-05 20:47:23 · 个人记录

这里是shadowice1984自用的板子

这里只是splay最基本的部分，并没有涉及到高端的部分……

tips:似乎只是需要注意0的father不一定是0就OK了？

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;
struct splaytree
{
    int s[N][2];int fa[N];
    inline int gc(int x){return s[fa[x]][1]==x;}
    inline void rt(int x)
    {
        int d=fa[x];int t=gc(x);
        s[d][t]=s[x][t^1];fa[s[x][t^1]]=d;
        s[fa[d]][gc(d)]=x;fa[x]=fa[d];
        s[x][t^1]=d;fa[d]=x;
    }
    inline void rtup(int x){rt(gc(x)^gc(fa[x])?x:fa[x]);rt(x);}
    inline void splay(int x){for(;fa[fa[x]]&&fa[x];rtup(x));if(fa[x]){rt(x);}}
}spt;