Splay 树简介

【Splay 树简介】
● Treap 树解决平衡的办法是给每个结点加上一个随机的优先级，实现概率上的平衡。Splay 树直接用旋转调整树的形态，通过旋转改善树的平衡性。计算量小，效果好。
● Splay 树的旋转主要分为“单旋”和“双旋”。
所谓“单旋”，即把结点 x 与它的父结点交换位置，使结点 x 上升一层。“单旋”不会减少树的层数，对改善平衡性没有帮助。根据旋转方向，“单旋”又分为左旋（zag）与右旋（zig）。
所谓“双旋”，即两次“单旋”。“双旋”同时旋转结点 x，父结点 f 及祖父结点 g 等3个结点，能改善平衡性。“双旋”又分为“一字旋”与“之字旋”。
● Splay 树的旋转示意图

● Splay 树的基本操作是把结点旋转到树的根部，这样下次访问它时，只需查一次就 OK 了。
● Splay 树是动态树（LCT，Link Cut Tree）与树链剖分的基础。
● Splay 树曾经是最常使用的 BST。不过，现在经常使用 FHQ Treap 树实现很多传统的 Splay 树的题目。因为，FHQ Treap 树代码更容易写，效率也很高，且可做持久化。

【Splay 树算法模板】
洛谷 P6136 代码：https://www.luogu.com.cn/problem/P6136

#include<bits/stdc++.h>
using namespace std;

const int maxn=1.1e6+5;
const int inf=(1<<30)+5;

struct Node {
    int ch[2];
    int p,v;
    int size;
    int cnt;
} tr[maxn];

int root,idx;

void pushup(int u) {
    tr[u].size=tr[tr[u].ch[0]].size+tr[tr[u].ch[1]].size+tr[u].cnt;
}

void rotate(int x) {
    int y=tr[x].p;
    int z=tr[y].p;
    int k=(tr[y].ch[1]==x);

    tr[y].ch[k]=tr[x].ch[k^1],tr[tr[x].ch[k^1]].p=y;
    tr[x].ch[k^1]=y,tr[y].p=x;
    tr[z].ch[tr[z].ch[1]==y]=x,tr[x].p=z;

    pushup(y);
    pushup(x);
}

void splay(int x, int k) {
    while(tr[x].p!=k) {
        int y=tr[x].p;
        int z=tr[y].p;

        if(z!=k) {
            if((tr[z].ch[1]==y) ^ (tr[y].ch[1]==x)) rotate(x);
            else rotate(y);
        }

        rotate(x);
    }

    if(!k) root=x;
}

void insert(int x) {
    int u=root, p=0;
    while(u && tr[u].v!=x) {
        p=u;
        u=tr[u].ch[x>tr[u].v];
    }
    if(u) tr[u].cnt++;
    else {
        u=++idx;
        if(p) tr[p].ch[x>tr[p].v]=u;
        tr[u].p=p;
        tr[u].v=x;
        tr[u].size=1;
        tr[u].cnt=1;
    }
    splay(u,0);
}

void find(int x) {
    int u=root;
    while(tr[u].ch[x>tr[u].v] && tr[u].v!=x) u=tr[u].ch[x>tr[u].v];
    splay(u,0);
}

int get_pre(int x) {
    find(x);
    if(tr[root].v<x) return root;
    int u=tr[root].ch[0];
    while(tr[u].ch[1]) u=tr[u].ch[1];
    splay(u,0);
    return u;
}

int get_suc(int x) {
    find(x);
    if(tr[root].v>x) return root;
    int u=tr[root].ch[1];
    while(tr[u].ch[0]) u=tr[u].ch[0];
    splay(u,0);
    return u;
}

void remove(int x) {
    int pre=get_pre(x);
    int suc=get_suc(x);

    splay(pre,0);
    splay(suc,pre);

    int del=tr[suc].ch[0];
    if(tr[del].cnt>1) tr[del].cnt--,splay(del,0);
    else tr[suc].ch[0]=0, splay(suc,0);
}

int get_rank_by_key(int x) {
    insert(x);
    int ans=tr[tr[root].ch[0]].size;
    remove(x);
    return ans;
}

int get_key_by_rank(int k) {
    int u=root;
    while(true) {
        if(k<=tr[tr[u].ch[0]].size) u=tr[u].ch[0];
        else if(k<=tr[tr[u].ch[0]].size+tr[u].cnt) break;
        else k-=tr[tr[u].ch[0]].size+tr[u].cnt, u=tr[u].ch[1];
    }
    splay(u,0);
    return tr[u].v;
}

int main() {
    insert(-inf);
    insert(inf);

    int n,T;
    cin>>n>>T;
    for(int i=1; i<=n; i++) {
        int x;
        cin>>x;
        insert(x);
    }

    int ans=0, last=0;

    while(T--) {
        int op,x;
        cin>>op>>x;
        x^=last;
        if(op==1) insert(x);
        else if(op==2) remove(x);
        else if(op==3) ans^=(last=get_rank_by_key(x));
        else if(op==4) ans^=(last=get_key_by_rank(x+1));
        else if(op==5) ans^=(last=tr[get_pre(x)].v);
        else ans^=(last=tr[get_suc(x)].v);
    }

    cout<<ans<<endl;

    return 0;
}

/*
in:
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4

out:
6
*/

【参考文献】
https://www.luogu.com.cn/problem/P6136
https://blog.csdn.net/SunnyYuanJiawei/article/details/129836238
https://www.cnblogs.com/baijian0212/p/splay.html
https://www.acwing.com/solution/content/50494/
https://blog.csdn.net/hnjzsyjyj/article/details/134728992
https://blog.csdn.net/hnjzsyjyj/article/details/120380473
https://zhuanlan.zhihu.com/p/348797577