BST树模板

一.Treap树

左旋和右旋
右旋：

旋转代码，son[0]是左儿子，son[1]是右儿子

void rotate(Node * &o,int d){                //d=0,左旋转；d=1，右旋转
        Node *k=o->son[d^1];                //d^1与1-d等价
        o->son[d^1]=k->son[d];             //相当于途中的between E and S
        k->son[d]=o;               
        o=k;                                //返回新的根
}

Treap树的删除
如果待删除的结点是叶子结点，直接删除就好了。
如果待删除的结点x有两个子结点，那么找到优先级最大的一个子结点，把x向相反的反向旋转，也就是把x向树的下层调整，直到x被旋转到叶子结点，然后直接删除。

题目的意思：是对一群人有一个等级和一个id，一开始有一个老大，老大的等级是最高的，然后后面每输入一个人，对他的等级进行排序，输出和他等级最接近的一个人的id，由于题目的n比较大，因此普通的排序不行。

#include<bits/stdc++.h>
using namespace std;
int id[5000000+5];
/*由随机函数产生每个结点的优先级，从而避免二叉树的形态退化成链表。
虽然不能保证每次生成的Treap树一定是平衡的，但是期望的插入,删除,插入的时间复杂度都是O(logn)的
kth和find与名次树有关，时间复杂度都是O(logn) 
*/ 
struct node{
    int size;                    //以这个结点为根的子树的结点总数量，用于名次树 
    int rank;                    //优先级
    int key;                    //键值 
    node *son[2];
    bool operator<(const node &a)const{return rank<a.rank;};
    int cmp(int x) {
        if(x==key)    return -1;
        return x<key?0:1;
    }
    inline void update() {        //更新size 
        size=1;
        if(son[0])    size+=son[0]->size;
        if(son[1])    size+=son[1]->size;
    }
};
void rotate(node* &o,int d) {    //d为0时左旋，d为1时右旋 
    node *k=o->son[d^1];        //如果d为0，k为o的右儿子，d^1与1-d等价，但是更快 
    o->son[d^1]=k->son[d];        //o的右儿子为k的左儿子 
    k->son[d]=o;                //k的左儿子为o 
    o->update();
    k->update(); 
    o=k;
}
void insert(node* &o,int x) {
    if(o) {                        //如果这个位置有结点了继续下去 
        int d=o->cmp(x);
        insert(o->son[d],x);
        ++o->size;
        if(o<o->son[d])
            rotate(o,d^1);
    }
    else {                        //这个位置没有结点，可以插入x 
        o=new node();
        o->son[0]=o->son[1]=NULL;
        o->rank=rand();
        o->key=x;
        o->size=1;
    }
}
int kth(node *o,int k) {
    if(k<=0||k>o->size)            //t-1和t+1可能不存在 
        return -1;
    int s=o->son[1]?o->son[1]->size:0;
    if(k==s+1) return o->key; 
    if(k<=s) kth(o->son[1],k);
    else    kth(o->son[0],k-s-1);
}
int find(node *o,int k) {
    int d=o->cmp(k);            //d为k在这个结点上的位置 
    if(d==-1)
        return o->son[1]?o->son[1]->size+1:1;
    if(d) find(o->son[d],k);
    else {                        //左子树要另外考虑 
        int tmp=find(o->son[0],k);
        if(tmp==-1)    return -1;
        return o->son[1]?o->son[1]->size+tmp+1:tmp+1;
    }
}
int main() {
    int n;
    while(~scanf("%d",&n)&&n) {
        srand(time(NULL));
        int k,g;
        scanf("%d%d",&k,&g);
        node *root=new node();
        root->son[0]=root->son[1]=NULL;
        root->rank=rand(); root->key=g; root->size=1;
        id[g]=k;
        printf("%d 1\n",k);
        for(int i=2;i<=n;++i) {
            scanf("%d%d",&k,&g);
            id[g]=k;
            insert(root,g);
            int t=find(root,g);
            int ans,ans1,ans2;
            ans1=kth(root,t-1);
            ans2=kth(root,t+1);
            if(ans1!=-1&&ans2!=-1) ans= ans1-g>=g-ans2?ans2:ans1;
            else if(ans2!=-1) ans=ans2;
            else ans=ans1;
            printf("%d %d\n",k,id[ans]);
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
int id[5000000+5];
struct node{
    int size;
    int rank;
    int key;
    node *son[2];
    bool operator<(const node &a)const{return rank<a.rank;};
    int cmp(int x) {
        if(x==key)    return -1;
        return x<key?0:1;
    }
    inline void update() {
        size=1;
        if(son[0])    size+=son[0]->size;
        if(son[1])    size+=son[1]->size;
    }
};
void rotate(node* &o,int d) {
    node *k=o->son[d^1];
    o->son[d^1]=k->son[d];
    k->son[d]=o;
    o->update();
    k->update(); 
    o=k;
}
void insert(node* &o,int x) {
    if(o) {
        int d=o->cmp(x);
        insert(o->son[d],x);
        ++o->size;
        if(o<o->son[d])
            rotate(o,d^1);
    }
    else { 
        o=new node();
        o->son[0]=o->son[1]=NULL;
        o->rank=rand();
        o->key=x;
        o->size=1;
    }
}
int kth(node *o,int k) {
    if(k<=0||k>o->size)
        return -1;
    int s=o->son[1]?o->son[1]->size:0;
    if(k==s+1) return o->key; 
    if(k<=s) kth(o->son[1],k);
    else    kth(o->son[0],k-s-1);
}
int find(node *o,int k) {
    int d=o->cmp(k);
    if(d==-1)
        return o->son[1]?o->son[1]->size+1:1;
    if(d) find(o->son[d],k);
    else {
        int tmp=find(o->son[0],k);
        if(tmp==-1)    return -1;
        return o->son[1]?o->son[1]->size+tmp+1:tmp+1;
    }
}
int main() {
    int n;
    while(~scanf("%d",&n)&&n) {
        srand(time(NULL));
        int k,g;
        scanf("%d%d",&k,&g);
        node *root=new node();
        root->son[0]=root->son[1]=NULL;
        root->rank=rand(); root->key=g; root->size=1;
        id[g]=k;
        printf("%d 1\n",k);
        for(int i=2;i<=n;++i) {
            scanf("%d%d",&k,&g);
            id[g]=k;
            insert(root,g);
            int t=find(root,g);
            int ans,ans1,ans2;
            ans1=kth(root,t-1);
            ans2=kth(root,t+1);
            if(ans1!=-1&&ans2!=-1) ans= ans1-g>=g-ans2?ans2:ans1;
            else if(ans2!=-1) ans=ans2;
            else ans=ans1;
            printf("%d %d\n",k,id[ans]);
        }
    }
}

二.Splay树

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int root;                                    //根
int rev[maxn],pre[maxn],size[maxn];
//rev[i],标记i被翻转;pre[i],i的父结点；size[i],i的子树上结点的个数
int tree[maxn][2];//记录树:tree[i][0],i的左儿子;tree[i][1],i的右儿子
struct node{
    int val,id;
    bool operator<(const node &A)const {    //用于sort排序 
        if(val==A.val) return id<A.id;
        return val<A.val;
    }
}nodes[maxn];
void pushup(int x) {                        //计算以x为根的子树包含多少子结点 
    size[x]=size[tree[x][0]]+size[tree[x][1]]+1;
}
void update_rev(int x) {                    //用标记的方式记录翻转情况，减少直接操作的次数，等Splay操作再处理 
    if(!x)    return;
    swap(tree[x][0],tree[x][1]);            //先翻转x:交换左右儿子 
    rev[x]^=1;                                //标记x被翻转--它的儿子还没翻 
}
/*结点是按照中序遍历创建的，所以左儿子是头，右儿子是尾，
机械臂翻转是调换头和尾，也就是左右儿子*/ 
void pushdown(int x) {                        //在做Splay时，根据本题的需要，处理机械臂翻转 
    if(rev[x]) {
        update_rev(tree[x][0]);
        update_rev(tree[x][1]);
        rev[x]=0;
    }
}
void Rotate(int x,int d) {                    //旋转，d=0为左旋，d=1为右旋 
    int y=pre[x];
    pushdown(y);
    pushdown(x);
    tree[y][!d]=tree[x][d];
    pre[tree[x][d]]=y;
    if(pre[y])
        tree[pre[y]][tree[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    tree[x][d]=y;
    pre[y]=x;
    pushup(y);
}
void splay(int x,int goal) {                //把结点x旋转为goal的儿子，如果goal是0，则旋转到根
    pushdown(x);            //是时候翻转x的儿子并且标记它的儿子了，防止x的儿子走了导致标记失效，以下都是 
    //一直选择，直到x成为goal的儿子
    while(pre[x]!=goal) if(pre[pre[x]]==goal) {
        pushdown(pre[x]); pushdown(x);
        Rotate(x,tree[pre[x]][0]==x);
    }//情况1:x的父结点是根，单旋一次即可 
    else {
        pushdown(pre[pre[x]]); pushdown(pre[x]); pushdown(x);
        int y=pre[x];
        int d=(tree[pre[y]][0]==y);
        if(tree[y][d]==x) {
            Rotate(x,!d);
            Rotate(x,d);
        }//情况(2): x、x的父、x的父的父，不共线 
        else {
            Rotate(y,d);
            Rotate(x,d);
        }//情况(3): x、x的父、x的父的父，共线 
    }//x的父结点不是根 
    pushup(x);
    if(goal==0)    root=x;    //如果goal是0，则将根节点更新为x 
}
int get_max(int x) {    //和找以当前结点为根树中的最大值一样的操作，只是本题的BST树有序结构会被打乱 
    pushdown(x);
    while(tree[x][1]) {
        x=tree[x][1];
        pushdown(x);
    }
    return x;
}
void del_root() {        //删除根结点 
    if(tree[root][0]==0) {    //因为机械手是翻转根节点的左子树，所以优先把左子树的结点移动根结点最好 
        root=tree[root][1];
        pre[root]=0;
    }
    else {                    //先把新根结点移到根，再取代旧的根结点 
        int m=get_max(tree[root][0]);
        splay(m,root);
        tree[m][1]=tree[root][1];
        pre[tree[root][1]]=m;
        root=m;
        pre[root]=0;
        pushup(root);
    }
}
void newnode(int &x,int fa,int val) {
    x=val;
    pre[x]=fa;
    size[x]=1;
    rev[x]=0;
    tree[x][0]=tree[x][1]=0;
}
void buildtree(int &x,int l,int r,int fa) {
    if(l>r) return;
    int mid=(l+r)>>1;
    newnode(x,fa,mid);
    buildtree(tree[x][0],l,mid-1,x);
    buildtree(tree[x][1],mid+1,r,x);
    pushup(x);
}
int main() {
    int n;
    while(~scanf("%d",&n)&&n) {
        buildtree(root,1,n,0);        //把初始位置按中序遍历1...n的顺序建立二叉树
        //结束后root=(n+1)/2,也就是树的根节点 
        for(int i=1;i<=n;++i) {        //val只用来排序，id为树的结点 
            scanf("%d",&nodes[i].val); nodes[i].id=i;
        }
        sort(nodes+1,nodes+n+1);
        for(int i=1;i<n;++i) {        //依次取出值最小的结点---取名x 
            splay(nodes[i].id,0);    //先将x提到根结点去 
            update_rev(tree[root][0]);//翻转结点x，对结点x做标记 
            printf("%d ",i+size[tree[root][0]]);//左边元素的个数就是它现在的位置 
            del_root();                //删除结点x，为了序列不变，先找到左子树最右的结点(可以理解为左子树最大的点) 
        }                            //注意，翻转会改变BST树的有序结构，所以最右边不一定是最大的点，找不到时取顶点 
        printf("%d\n",n);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int root;
int rev[maxn],pre[maxn],size[maxn];
int tree[maxn][2];
struct node{
    int val,id;
    bool operator<(const node &A)const {
        if(val==A.val) return id<A.id;
        return val<A.val;
    }
}nodes[maxn];
void pushup(int x) {
    size[x]=size[tree[x][0]]+size[tree[x][1]]+1;
}
void update_rev(int x) {
    if(!x)    return;
    swap(tree[x][0],tree[x][1]);
    rev[x]^=1;
}
void pushdown(int x) {
    if(rev[x]) {
        update_rev(tree[x][0]);
        update_rev(tree[x][1]);
        rev[x]=0;
    }
}
void Rotate(int x,int d) {
    int y=pre[x];
    pushdown(y);
    pushdown(x);
    tree[y][!d]=tree[x][d];
    pre[tree[x][d]]=y;
    if(pre[y])
        tree[pre[y]][tree[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    tree[x][d]=y;
    pre[y]=x;
    pushup(y);
}
void splay(int x,int goal) {
    pushdown(x);
    while(pre[x]!=goal) if(pre[pre[x]]==goal) {
        pushdown(pre[x]); pushdown(x);
        Rotate(x,tree[pre[x]][0]==x);
    }
    else {
        pushdown(pre[pre[x]]); pushdown(pre[x]); pushdown(x);
        int y=pre[x];
        int d=(tree[pre[y]][0]==y);
        if(tree[y][d]==x) {
            Rotate(x,!d);
            Rotate(x,d);
        }
        else {
            Rotate(y,d);
            Rotate(x,d);
        }
    }
    pushup(x);
    if(goal==0)    root=x;
}
int get_max(int x) {
    pushdown(x);
    while(tree[x][1]) {
        x=tree[x][1];
        pushdown(x);
    }
    return x;
}
void del_root() {
    if(tree[root][0]==0) { 
        root=tree[root][1];
        pre[root]=0;
    }
    else {
        int m=get_max(tree[root][0]);
        splay(m,root);
        tree[m][1]=tree[root][1];
        pre[tree[root][1]]=m;
        root=m;
        pre[root]=0;
        pushup(root);
    }
}
void newnode(int &x,int fa,int val) {
    x=val;
    pre[x]=fa;
    size[x]=1;
    rev[x]=0;
    tree[x][0]=tree[x][1]=0;
}
void buildtree(int &x,int l,int r,int fa) {
    if(l>r) return;
    int mid=(l+r)>>1;
    newnode(x,fa,mid);
    buildtree(tree[x][0],l,mid-1,x);
    buildtree(tree[x][1],mid+1,r,x);
    pushup(x);
}
int main() {
    int n;
    while(~scanf("%d",&n)&&n) {
        buildtree(root,1,n,0);
        for(int i=1;i<=n;++i) {
            scanf("%d",&nodes[i].val); nodes[i].id=i;
        }
        sort(nodes+1,nodes+n+1);
        for(int i=1;i<n;++i) {
            splay(nodes[i].id,0);
            update_rev(tree[root][0]);
            printf("%d ",i+size[tree[root][0]]);
            del_root();
        }
        printf("%d\n",n);
    }
    return 0;
}