文艺平衡树（splay模板）

题干：splay模板，要求维护区间反转。

splay是一种码量小于treap，但支持排名，前驱后继等treap可求的东西，也支持区间反转的平衡树。

但是有两个坏处：

1.splay常数远远大于treap以及stl中的set。

2.没有可持久化splay，但有可持久化treap。

下面是代码：

1.pushup以及pushdown

pushup用于维护某点所在子树大小。

void pushup(int u)

{

    tr[u].siz = tr[tr[u].ch[]].siz + tr[tr[u].ch[]].siz + ;

}

一行。

pushdown用于标记下推。

void pushdown(int u)

{

    if(tr[u].mrk)

    {

        tr[u].mrk=;

        swap(tr[u].ch[],tr[u].ch[]);

        tr[tr[u].ch[]].mrk^=;

        tr[tr[u].ch[]].mrk^=;

    }

}

2.rotate

rotate相当于treap中的lturn和rturn，是将x点转到他的父节点处。

void rotate(int x)

{

    int y = tr[x].fa;

    int z = tr[y].fa;

    int k = (tr[y].ch[]==x);

    tr[x].fa = z,tr[z].ch[tr[z].ch[]==y]=x;

    tr[y].ch[k] = tr[x].ch[k^],tr[tr[x].ch[k^]].fa = y;

    tr[y].fa = x,tr[x].ch[k^]=y;

    pushup(y),pushup(x);

}

注意改变父子关系时的顺序问题，还有两个pushup，应该先pushup儿子后pushup父亲。

3.splay（splay核心操作）

splay（a，b），将a旋转到b的儿子处。

下面是双旋splay：

void splay(int x,int goal)

{

    while(tr[x].fa!=goal)

    {

        int y = tr[x].fa;

        int z = tr[y].fa;

        if(z!=goal)

            ((tr[z].ch[]==y)^(tr[y].ch[]==x))?rotate(x):rotate(y);

        rotate(x);

    }

    if(goal==)rot=x;

}

代码中while中的if，机房普遍认为是为了维护整棵树的深度。

4.insert

码量比treap少很多：

void insert(int x)

{

    int u = rot,fa;

    while(u)fa=u,u=tr[u].ch[tr[u].v<x];

    u=++tot;

    if(fa)tr[fa].ch[x>tr[fa].v]=u;

    tr[u].fa = fa,tr[u].v = x,tr[u].siz = ;

    splay(u,);

}

5.查询排名

代码：

int query_kth(int k)

{

    int u = rot;

    while()

    {

        pushdown(u);

        int t = tr[tr[u].ch[]].siz;

        if(t==k-)return u;

        else if(t>=k)u=tr[u].ch[];

        else k-=t+,u=tr[u].ch[];

    }

}

6.区间旋转

先查询前驱后继，然后把所在子树夹到前驱后继之间，一个标记解决问题。

void chg(int l,int r)

{

    l = query_kth(l);//前驱

    r = query_kth(r+);//后继

    splay(l,);splay(r,l);

    tr[tr[tr[rot].ch[]].ch[]].mrk^=;

}

最后：

推极大极小,推极大极小，推极大极小！！！

全代码就不粘了。