模板来源：Luogu P3369 普通平衡树
分享一张好看的图 w 来自 jvlao@kakakakakaka

没有水印就完美了....

原题解来自 @huangwenlong 的洛谷博客：传送门
题解写的很好，能看懂。
然而第一次打的时候由于是对着模板打的，有一些不符合自己编程习惯的细节与我本身的习惯冲突了。
所以打了第二遍模板。相对来说要简洁一点，并且对一些操作的步骤做了微小的改变。

嘛，对于模板，还是更建议：首先在纸上总结一些流程，可以来个图解。然后再用代码实现，不懂的实现细节再来参考代码。这或许是一种更好的学习方式。

Code

// Code by ajcxsu
// Problem: splay
// verb

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

inline void gn(int &x) {
    x=0;
    int pl=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl;
}

struct Node *nil;
struct Node {
    int val,c,s; // v cnt size
    Node *ch[2];
    Node(int val=0):val(val),c(1),s(1) { ch[0]=ch[1]=nil; }
    int cmp(int v) {
        if(val==v) return -1;
        else return v>val;
    }
    void upd() {
        s=c+ch[0]->s+ch[1]->s;
    }
} *root;
void ini() {
    nil=new Node(-0x3f3f3f3f);
    root=nil->ch[0]=nil->ch[1]=nil;
    nil->c=nil->s=0;
}

void rot(Node *&x, bool type) {
    Node *t=x->ch[type];
    x->ch[type]=t->ch[!type];
    t->ch[!type]=x;
    x->upd(), t->upd();
    x=t;
}

void splay(Node *&x, int v) {
    int d=x->cmp(v);
    if(d!=-1 && x->ch[d]!=nil) {
        int d2=x->ch[d]->cmp(v);
        if(d2!=-1 && x->ch[d]->ch[d2]!=nil) {
            splay(x->ch[d]->ch[d2],v);
            if(d==d2) rot(x,d), rot(x,d);
            else rot(x->ch[d],d2), rot(x,d);
        }
        else rot(x,d);
    }
}

int kth(int k, Node *x=root) {
    if(x==nil || k<0 || k>x->s) return -1;
    int ss=x->ch[0]->s;
    if(k>=ss+1 && k<=ss+x->c) return x->val;
    else if(k>ss+x->c) return kth(k-ss-x->c, x->ch[1]);
    else return kth(k, x->ch[0]);
}

int rank(int v) {
    splay(root, v);
    return root->ch[0]->s+1;
}
#define INF (0x3f3f3f3f)

int lower(int v) {
    splay(root, v);
    if(root->val >= v) {
        splay(root->ch[0], INF);
        return root->ch[0]->val;
    }
    else return root->val;
}

int upper(int v) {
    splay(root, v);
    if(root->val <= v) {
        splay(root->ch[1], -INF);
        return root->ch[1]->val;
    }
    else return root->val;
}

Node* split(Node *&x, int v) {
    splay(x,v);
    Node *x1,*x2;
    if(x->val <=v) x1=x, x2=x->ch[1], x->ch[1]=nil;
    else x1=x->ch[0], x2=x, x->ch[0]=nil;
    x->upd();
    x=x1;
    return x2;
}

void merge(Node *&x1, Node*&x2) {
    if(x1==nil) swap(x1,x2);
    splay(x1,INF);
    x1->ch[1]=x2, x1->upd();
    x2=nil;
}

void ins(int v) {
    Node *x2=split(root,v);
    if(root->val==v) root->c++;
    else {
        Node *nd=new Node(v);
        merge(root,nd);
    }
    merge(root,x2);
}

void del(int v) {
    splay(root, v);
    if(!(--root->c)) {
        Node *nd=root;
        root=root->ch[0], merge(root,nd->ch[1]);
        delete nd;
    }
}

int main() {
    ini();
    int n;
    gn(n);
    int opt,val;
    while(n--) {
        gn(opt), gn(val);
        if(opt==1) ins(val);
        else if(opt==2) del(val);
        else if(opt==3) printf("%d\n",rank(val));
        else if(opt==4) printf("%d\n",kth(val));
        else if(opt==5) printf("%d\n",lower(val));
        else if(opt==6) printf("%d\n",upper(val));
    }
    return 0;
}

UPD 维护父指针版

忽然就发现 Splay 有些题是必须要维护父指针的.... 比如查询某个序列的某个值，但你并不知道这个东西的排名_(:зゝ∠)_于是你就要维护这个值在树中的指针，于是就必须写 splay 自底向上的非递归版本，于是就必须写维护父指针的版本 Orz
没错我说的就是那个什么 书架 。

有几个要点：
该清零的指针要清零。不然 gg。
该更新的指针更新。不要引用。
该要判空指针的判空指针。不要懒。
这就是为什么父指针版很辣鸡的原因。

也许之后会有更好的版本吧。

// code by ajcxsu
// Problem: splay
// verD

#include<bits/stdc++.h>
using namespace std;
#define INF (0x7fffffff)
struct Node *nil;
struct Node {
    int v,s,c;
    Node *ch[2],*f;
    Node(int v=0) :v(v),s(1),c(1) { ch[0]=ch[1]=f=nil; }
    int dir() {
        if(f==nil) return -1;
        return f->ch[1]==this;
    }
    int cmp(int val) {
        if(val==v) return -1;
        return val>v;
    }
    void upd() { s=c+ch[0]->s+ch[1]->s; }
} *root;
void init() {
    nil=new Node(-INF);
    root=nil->ch[0]=nil->ch[1]=nil->f=nil;
    nil->s=nil->c=0;
}
void dfs(Node *x) {
    if(x==nil) {
        printf("BACK\n");
        return;
    }
    printf("%d\n",x->v);
    printf("GOLEFT\n"), dfs(x->ch[0]);
    printf("GORIGHT\n"), dfs(x->ch[1]);
    printf("BACK\n");
} // 调试函数

void rot(Node *x) {
    Node *y=x->f;
    int d=x->dir();
    if(d==-1) return;
    /* 改y的子树 */
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    /* 改z的子树 */
    x->f=y->f;
    if(y->f!=nil) y->f->ch[y->dir()]=x;
    /* 改x的子树 */
    x->ch[!d]=y, y->f=x;
    if(y==root) root=x;
    y->upd();
}

void splay(Node *f, Node *x) { // x 旋到 f 下面 (旋到根是旋到nil下面)
    while(x->f!=f) {
        Node *y=x->f, *z=y->f;
        if(z==f) rot(x);
        else if(x->dir()==y->dir()) rot(y),rot(x);
        else rot(x),rot(x);
    }
    x->upd();
}

Node *find(Node *x,int val) {
    int d=x->cmp(val);
    if(d==-1 || x->ch[d]==nil) return x;
    else return find(x->ch[d], val);
}

Node *split(Node *&x,int val) {
    splay(nil,find(x,val));
    Node *x1,*x2;
    if(root->v<=val) x1=x, x2=x->ch[1], x2->f=nil, x->ch[1]=nil;
    else x1=x->ch[0], x2=x, x1->f=nil, x->ch[0]=nil;
    x->upd();
    x=x1;
    return x2;
}
void merge(Node *&x1,Node *&x2) {
    if(x1==nil) swap(x1,x2);
    splay(x1->f,find(x1,INF));
    x1->ch[1]=x2, x2->f=x1, x1->upd();
    if(x2==nil) x2->f=nil; // 如果x2是nil，此处应该重置
    x2=nil;
}

void ins(int val) {
    Node *x2=split(root,val);
    if(root->v==val) root->c++;
    else {
        Node *nd=new Node(val);
        merge(root,nd);
    }
    merge(root,x2);
}

void del(int val) {
    splay(nil,find(root,val));
    if(!(--root->c)){
        Node *nd=root;
        root=root->ch[0];
        root->f=nd->ch[1]->f=nil; // 右子树的头指针请一定置为nil
        merge(root, nd->ch[1]);
        delete nd;
    }
}

int rank(int val) {
    splay(nil,find(root,val));
    return root->ch[0]->s+1;
}

int kth(Node *x, int k) {
    int ss=x->ch[0]->s;
    if(k<=ss) return kth(x->ch[0],k);
    else if(k<=ss+x->c) return x->v;
    else return kth(x->ch[1],k-ss-x->c);
}

int lower(int val) {
    splay(nil,find(root,val));
    if(root->v >= val) {
        splay(root,find(root->ch[0],INF));
        return root->ch[0]->v;
    }
    return root->v;
}

int upper(int val) {
    splay(nil,find(root,val));
    if(root->v <=val) {
        splay(root,find(root->ch[1],-INF));
        return root->ch[1]->v;
    }
    return root->v;
}

inline void gn(int &x) {
    x=0;
    int pl=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl;
}


int main() {
    init();
    int n;
    gn(n);
    int opt,val;
    while(n--) {
        gn(opt), gn(val);
        if(opt==1) ins(val);
        else if(opt==2) del(val);
        else if(opt==3) printf("%d\n",rank(val));
        else if(opt==4) printf("%d\n",kth(root,val));
        else if(opt==5) printf("%d\n",lower(val));
        else if(opt==6) printf("%d\n",upper(val));
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/splay.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆