洛谷P3369 splay或treap

题目链接:https://www.luogu.org/problemnew/show/P3369

推荐博客(splay):https://blog.csdn.net/A_Comme_Amour/article/details/79382104#commentBox

推荐博客(treap):https://blog.csdn.net/yang_yulei/article/details/46005845

贴两个板子(仅供参考),加点注释,以后也好抄,至于更加详细的,看头顶大佬,我比较lj。

splay代码(数组版本):

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque> 
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 100005
int ch[maxn][2],fa[maxn],size[maxn],cnt[maxn],val[maxn];
int root,num;
int n,m,k,t; 
int add(int x,int pre){//增加一个节点 
    ++num;
    ch[num][0]=ch[num][1]=0;
    size[num]=cnt[num]=1;
    val[num]=x;
    fa[num]=pre;
    if(pre) 
    ch[pre][val[pre]<x]=num;
    return num;
}
void update(int x){
    size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
}
int find_pre(int x){
    int now=root,pre=0;//pre储存当前最优解
    while(now){
        if(val[now]<x){//如果当前点的值小于x,那么更新pre 
            pre=now;
            now=ch[now][1];//向右走,看看能不能找到更加优的 
        }else{
            now=ch[now][0];//如果当前节点值大于x,向左走 
        }
    } 
    return pre;//返回最后找到的最优解就是x的前缀前驱 
}
int find_suf(int x){
    int now=root,pre=0;//原理同上 
    while(now){
        if(val[now]>x){
            pre=now;
            now=ch[now][0];
        }else{
            now=ch[now][1]; 
        } 
    }
    return pre;
}
void rotate(int x){
    int pre=fa[x];//x的父亲 
    int ppre=fa[pre];//x的祖先 
    int a=(ch[pre][1]==x);//x是pre的哪一个儿子 
    int b=(ch[ppre][1]==pre);//pre是ppre的哪一个儿子 
    ch[pre][a]=ch[x][a^1],fa[ch[x][a^1]]=pre;//处理pre和x的儿子(ch[x][a^1])之间关系 
    ch[x][a^1]=pre,fa[pre]=x;//处理pre和x之间的关系 
    fa[x]=ppre;//处理x和ppre之间的关系 
    if(ppre) ch[ppre][b]=x;
    update(pre);//pre变成了x的儿子,先更新深度小的节点 
    update(x);//更新到x就可以了,至于ppre,即现在x的父亲的信息将在splay的下一次旋转中进行更新 
}
void splay(int x,int goal){
    while(fa[x]!=goal){
        int pre=fa[x];
        int ppre=fa[pre];
        if(ppre!=goal)//如果父亲的父亲不是goal,就说明至少还要旋转两次 
        (ch[ppre][1]==pre)^(ch[pre][1]==x)?rotate(x):rotate(pre);//左边两个布尔值异或,假如三个点共线(不太专业的表达),第一次先旋转pre,否则旋转x 
        rotate(x);//第二次旋转都是旋转x 
    }
    if(goal==0)//更新根节点 
    root=x;
}
void insert(int x){
    int now=root,pre=0,d;
    while(now&&val[now]!=x){
        d=val[now]<x;
        pre=now;
        now=ch[now][d];
    }
    if(now==0){
        now=add(x,pre);
    }else{
        cnt[now]++; 
        update(now);//假如现在的now就是root,那么它将不会旋转,那么这里就需要一个更新操作,把root的信息更新 
        //但是这一句我删掉了还是可以过 
    }
    splay(now,0);//splay不仅仅只是把now旋转到根节点,旋转的同时他也保证了节点信息的实时更新(我觉得root这个点有时候不能保证,仅限于我这份代码) 
}
void del(int x){
    int now=root;
    while(now&&val[now]!=x){//寻找值为x的点 
        int d=val[now]<x;
        now=ch[now][d];
    }
    if(now==0) return;//如果不存在x这个数 
    if(cnt[now]>1){
        cnt[now]--;
        update(now);
        splay(now,0); 
        return;
    }else{
        splay(now,0);
        if(!ch[root][0]&&!ch[root][1]){//没有儿子,直接删除 
            root=0;
            return;
        }else if(ch[root][0]==0||ch[root][1]==0){//只有一个儿子 
            root=max(ch[root][0],ch[root][1]);//把那个儿子直接变成根节点 
            fa[root]=0;//不要忘记了把根节点的父亲改成0 
        }else{//两个儿子都有 
            int pre=find_pre(x);//找x的前驱 
            int suf=find_suf(x);//找x的后驱 
            splay(pre,0);//把左儿子旋转到根节点,此时做儿子变成了根节点 
            splay(suf,pre);//把右儿子旋转到左儿子的下面,也就是说右儿子变成了左儿子的右儿子 
            ch[suf][0]=0;//此时now就是suf的左儿子,因为now大于当前根节点,小于当前根节点的右儿子 
            update(suf);//suf的左儿子没了,更新 
            update(pre);//爸爸也更新 
        }
    }
}
int rank(int x){ 
    int ans=0,now=root;
    while(now&&val[now]!=x){
        int d=val[now]<x;
        if(d==1)
        ans+=size[ch[now][0]]+cnt[now];//如果当前值比x小,那么要向右儿子方向走,当前点和它的左子树的点都小于x 
        now=ch[now][d];
    }
    ans+=size[ch[now][0]];//现在找到了x,但是当前now可能还有左子树,所以要加上当前now的左子树大小 
    splay(now,0);//每次操作都要把操作的点旋转到根节点,这个也要,我测了一下,这个要是不加,最后一组数据超时 
    return ans+1;
}
int arank(int now,int x){//查询排名为x的点的值,递归写法
    if(now==0) return 0;
    if(size[ch[now][0]]>=x)//如果左子树的大小大于等于x,那么向左子树方向找 
    return arank(ch[now][0],x);
    else if(size[ch[now][0]]+cnt[now]>=x){//当前点的数量加上左子树大小大于等于x,前面左子树大小是小于x的,那么就是当前点了 
        splay(now,0); //旋转到根 
        return val[now];
    }else
    return arank(ch[now][1],x-size[ch[now][0]]-cnt[now]);//向右子树找第x-size[ch[now][0]]-cnt[now]大的点的值 
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        root=num=0;
        int op,x;
        for(int i=0;i<n;i++){
            scanf("%d%d",&op,&x);
            if(op==1){
                insert(x);
            }else if(op==2){
                del(x);
            }else if(op==3){
                printf("%d
",rank(x));
            }else if(op==4){
                printf("%d
",arank(root,x));
            }else if(op==5){
                printf("%d
",val[find_pre(x)]);
            }else if(op==6){
                printf("%d
",val[find_suf(x)]);
            }
        }
    }
    return 0;
}

 treap(数组版本):

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque> 
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 100005
int ch[maxn][2],size[maxn],cnt[maxn],rank[maxn],val[maxn];
int n,m,k,t,num,root;
int add(int x){
    ++num;
    ch[num][0]=ch[num][1]=0;
    size[num]=cnt[num]=1;
    val[num]=x;
    rank[num]=rand()%(maxn*100+1);//给num一个随机的优先级,这里对maxn*100+1取模没有什么特殊含义 
    return num;
}
void update(int x){
    if(x)
    size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
}
void rotate(int &x,int d){//将ch[x][d]旋转到x的位置上面 
    int temp=ch[x][d];
    ch[x][d]=ch[temp][d^1];
    ch[temp][d^1]=x;
    x=temp;//这里的x是引用,所以可以直接修改,不需要父亲节点的参与了 
    update(ch[x][d^1]);//之前的x变成了temp的儿子,先更新深度更小的点 
    update(x);
}
void insert(int &root,int x){
    if(root==0){
        root=add(x);//增加一个节点 
        return;
    }else if(val[root]==x){
        cnt[root]++;
    }else{
        int d=(val[root]<x);
        insert(ch[root][d],x);
        if(rank[root]<rank[ch[root][d]]){//假如ch[root][d]的优先级大于root,那么就要把它旋转到root的位置上面 
            rotate(root,d);
        }
    }
    update(root);//记得更新 
}
void del(int &root,int x){
    if(root==0) return;//不存在,就返回 
    if(val[root]==x){
        if(cnt[root]>1){
            cnt[root]--;
            update(root);
            return;
        }else{
            if(!ch[root][0]&&!ch[root][1]){//假如没有儿子,说明已经是叶子了,直接删除 
                root=0;
            }else if(rank[ch[root][0]]>rank[ch[root][1]]){//调一个优先级大的儿子,把root向叶子节点旋转 
                rotate(root,0);//右旋,把左儿子旋转到root 
                del(ch[root][1],x);//旋转之后之前的root在当前root的右边了,向右找x删除 
            }else{
                rotate(root,1);//左旋 
                del(ch[root][0],x);//值为x的点跑到当前root的左儿子上面去了 
            } 
        }
        update(root);//更新,返回 
        return;
    }
    int d=val[root]<x;//当前节点不等于x,判断是向左还是向右 
    del(ch[root][d],x);
    update(root); 
}
int get_rank(int root,int x){
    int ans=0;
    while(root&&val[root]!=x){//root为0或找到x为止 
        int d=val[root]<x;
        if(d==1)//如果d==1,说明当前root的自己包括他的左子树上的点的大小都小于x,那么这些点都要加上 
        ans+=size[ch[root][0]]+cnt[root];
        root=ch[root][d];
    }
    ans+=size[ch[root][0]];//当前值为x的点可能还有左子树,所以要加上左子树的大小 
    if(root==0) return 0;//不存在 
    return ans+1;//记得加1 
}
int arank(int root,int x){
    if(size[ch[root][0]]>=x)//左子树的大小大于等于x,向左子树方向找 
    return arank(ch[root][0],x);
    else if(size[ch[root][0]]+cnt[root]>=x)//前面的左子树大小 小于x,现在加上root这个点的数量大于等于x,那么就是root这个点的值 
    return val[root];
    else //否则,向右子树找,但是要减去root和左子树的数量,因为它们都比x小 
    return arank(ch[root][1],x-size[ch[root][0]]-cnt[root]);
}
int find_pre(int root,int x){
    int pre=0;//pre保存当前最优解 
    while(root){
        if(val[root]<x){//如果当前节点的值小于x,更新pre,向右走,看能不能找到更优的 
            pre=root;
            root=ch[root][1];
        }else{//大于等于就向左走 
            root=ch[root][0];
        }
    }
    return val[pre];
}
int find_suf(int root,int x){
    int pre=0;//同上 
    while(root){
        if(val[root]>x){
            pre=root;
            root=ch[root][0];
        }else{
            root=ch[root][1];
        }
    }
    return val[pre];
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        int op,x;
        num=0,root=0;
        for(int i=0;i<n;i++){
            scanf("%d%d",&op,&x);
            if(op==1){
                insert(root,x);
            }else if(op==2){
                del(root,x);
            }else if(op==3){
                printf("%d
",get_rank(root,x));
            }else if(op==4){
                printf("%d
",arank(root,x)); 
            }else if(op==5){
                printf("%d
",find_pre(root,x));
            }else if(op==6){
                printf("%d
",find_suf(root,x));
            }
        }
    }
    return 0;
}

splay代码(结构体版本,又长又臭,不保证没有问题,因为这是我第一次写的splay):

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque> 
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 100100
struct node{
    int value,fa,sum,cnt;//值,当前节点的父亲,当前节点的子树大小,cnt表示value出现的次数 
    int son[2];//0代表左儿子,1代表右儿子 
}tree[maxn*2];
int n,m,k,t,root,cnt;
void init(){
    cnt=0;
    root=0;
}
void update(int now){
    if(now)
    tree[now].sum=tree[now].cnt+tree[tree[now].son[0]].sum+tree[tree[now].son[1]].sum;
    //cout<<tree[now].value<<' '<<tree[now].sum<<"***"<<endl;
}
void rotate(int x){//旋转x 
    int fa=tree[x].fa;
    int fafa=tree[fa].fa;
    int a=(tree[fa].son[1]==x);//a是0代表x是fa的左子树,1则是右子树 
    int b=(tree[fafa].son[1]==fa);//同上
    tree[fa].son[a]=tree[x].son[a^1],tree[tree[x].son[a^1]].fa=fa;//处理fa和x的儿子 
    tree[x].son[a^1]=fa,tree[fa].fa=x;//处理x和fa 
    tree[x].fa=fafa;//处理fafa和x 
    if(fafa){//假如fafa不为0,即存在,那么更新他的儿子 
        tree[fafa].son[b]=x;
    }
    update(fa);//注意这里要先更新fa,再更新x,因为旋转之后fa是x的儿子,所以先更新深度大的fa 
    update(x);
}
void splay(int x,int to){//将根节点旋转到to的儿子节点上  
    int now=x;
    while(now&&tree[now].fa!=to){
        int fa=tree[now].fa;
        int fafa=tree[fa].fa;
        if(fafa!=to)//如果父亲的父亲不是to,那么就要双旋,判断是哪种双旋 
        //如果是LL或RR,那么就是先旋转fa,再旋转x,如果是LR或者RL,那么两次都是旋转x 
        (tree[fa].son[1]==x)^(tree[fafa].son[1]==fa)?rotate(x):rotate(fa);
        rotate(x);
    } 
    if(to==0)//每次把一个节点移动到根节点上面就要更新root 
    root=x;
} 
void insert(int x){//插入一个数字x 
    int now=root,fa=0;//一开始从根节点开始找,根节点父亲为0 
    while(now&&tree[now].value!=x){//一直向下找x 
        fa=now;
        now=tree[now].son[tree[now].value<x];//选择左右儿子其中一个,向下走 
    }
    if(now){//如果已经有了x 
        tree[now].cnt++;//数量加1
        update(now); 
    }else{//之前没有就增加节点 
        now=++cnt;
        tree[now].cnt=1;
        tree[now].fa=fa;
        tree[now].son[0]=tree[now].son[1]=0;
        tree[now].value=x;
        tree[now].sum=1;
        if(fa)//更新fa的儿子 
        tree[fa].son[tree[fa].value<x]=now;
    }
    splay(now,0);//将now旋转到根节点上面 
}
int find(int x){//找到x的位置 
    int now=root;
    while(now&&tree[now].value!=x){
        now=tree[now].son[tree[now].value<x];
    }
    splay(now,0);
    return now;
}
int find_pre(int x){//找到x的前驱 
    int now=root;//x已经在根节点了,从x的左儿子上一直向右找,就是x的前缀 
    now=tree[now].son[0];
    while(tree[now].son[1]){
        now=tree[now].son[1];
    }
    return now;
} 
int find_suf(int x){//找到x的后驱 
    int now=root;
    now=tree[now].son[1];
    while(tree[now].son[0]){
        now=tree[now].son[0];
    }
    return now;
}
void destroy(int x){
    tree[x].cnt=tree[x].fa=tree[x].sum=tree[x].value=tree[x].son[0]=tree[x].son[1]=0;
}
void del(int x){
    int now=find(x);
    if(now==0) return;
    if(tree[now].cnt>1){//如果x的数量不止1个,则数量减1 
        tree[now].cnt--;
        update(now);//因为上面cnt减1,所以这里要更新一次now 
        return;
    }else{
        if(!tree[now].son[0]&&!tree[now].son[1]){//左右子树不存在 
            root=0;
            return;
        }else if(!tree[now].son[0]){//左子树不存在 
            root=tree[now].son[1];
            tree[root].fa=0;
            destroy(now);
            return; 
        }else if(!tree[now].son[1]){//右子树不存在 
            root=tree[now].son[0];
            tree[root].fa=0;
            destroy(now);
            return;
        }
        int pre=find_pre(x);
        splay(pre,0);//把前驱旋转到根节点
        tree[root].son[1]=tree[now].son[1];//根节点的右子树变成now的右子树
        tree[tree[root].son[1]].fa=root;//更新右子树的父亲
        destroy(now);
        update(root);//一定要更新根节点 
    }
}
int rank(int x){
    int ans=0;
    int now=root;
    while(now&&tree[now].value!=x){//
        if(tree[now].value<x)//如果当前节点的值小于x,那么当前节点和他的左子树的点都小于x,都要加上 
        ans+=tree[tree[now].son[0]].sum+tree[now].cnt;
        now=tree[now].son[tree[now].value<x];
    }
    ans+=tree[tree[now].son[0]].sum;
    splay(now,0);
    return ans+1;
}
int arank(int x){
    if(tree[root].sum<x)
    return 0;
    int now=root;
    while(now&&x>0){
        if(tree[now].son[0]&&tree[tree[now].son[0]].sum>=x){
            now=tree[now].son[0];
        }else if(tree[now].sum-tree[tree[now].son[1]].sum>=x){
            break;
        }else{
            x-=tree[now].sum-tree[tree[now].son[1]].sum;
            now=tree[now].son[1];
        }
    }
    splay(now,0);
    return tree[now].value;
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        int op,x;
        init();
        for(int i=1;i<=n;i++){
            scanf("%d%d",&op,&x);
            if(op==1){
                insert(x);
            }else if(op==2){
                del(x);
            }else if(op==3){
                printf("%d
",rank(x));
            }else if(op==4){
                printf("%d
",arank(x));
            }else if(op==5){
                insert(x);
                printf("%d
",tree[find_pre(x)].value);
                del(x);
            }else if(op==6){
                insert(x);
                printf("%d
",tree[find_suf(x)].value);
                del(x);
            }
        }
    }
    return 0;
}

 treap代码(结构体版本,又长又臭,不保证没有问题,因为(同上)):

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque> 
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 100005
struct node{
    int cnt,sum,rank,value;
    int son[2];
}tree[maxn]; 
int n,m,k,t,cnt;
int add(int value){//增加一个节点 
    int index=++cnt;
    tree[index].son[0]=tree[index].son[1]=0;
    tree[index].value=value;
    tree[index].sum=tree[index].cnt=1;
    tree[index].rank=rand()%(maxn*100)+1;
    return index;
}
void update(int x){
    tree[x].sum=tree[tree[x].son[0]].sum+tree[tree[x].son[1]].sum+tree[x].cnt;
}
void rotate(int &root,int d){//root和它的son[d]之间旋转 
    int temp=tree[root].son[d];
    tree[root].son[d]=tree[temp].son[d^1];
    tree[temp].son[d^1]=root;
    root=temp;//根节点换成temp 
    update(tree[root].son[d^1]);//之前的root变成了现在root的d^1方向的儿子,先更新深度小的点 
    update(root); 
}
void insert(int &root,int value){
    if(root==0){ 
        root=add(value);
        return;
    }
    if(tree[root].value==value){//已经存在value,则数量加1 
        tree[root].cnt++;
    }else{//不存在value 
        int d=tree[root].value<value?1:0;//判断向左还是向右 
        insert(tree[root].son[d],value);//递归插入 
        if(tree[root].rank>tree[tree[root].son[d]].rank){//向son[d]的方向走,所以只有son[d]的优先级有可能小于自己 
            rotate(root,d);
        }
    }
    update(root);//更新 
}
void del(int &root,int value){
    if(!root) return;
    if(tree[root].value==value){//找到了这个点 
        if(tree[root].cnt>1){
            tree[root].cnt--;
            update(root);
            return;
        }else{//当前值为value的节点的数量为1 
            if(tree[root].son[0]==0&&tree[root].son[1]==0){//没有儿子,直接删除 
                root=0;
                return;
            }else if(tree[tree[root].son[0]].rank<tree[tree[root].son[1]].rank){
            //一开始就把0的优先级设为无穷大了,比较 两个儿子的优先级,把优先级小的儿子旋转到当前点 
                rotate(root,0);//右旋 
                del(tree[root].son[1],value);//右旋之后,之前的root是新的root的右儿子 
            }else{
                rotate(root ,1);//左旋 
                del(tree[root].son[0],value);
            }
            update(root);//血的教学,注意更新 
            return; 
        }
    }
    int d=tree[root].value<value?1:0;//教继续向下找 
    del(tree[root].son[d],value);
    update(root);//注意更新 
}
int rank(int root,int x){
    int ans=0;
    while(root&&tree[root].value!=x){
        int d=tree[root].value<x?1:0;
        if(d==1)
        ans+=tree[root].sum-tree[tree[root].son[1]].sum;
        root=tree[root].son[d];
    }
    if(root==0)
    return 0;
    ans+=tree[tree[root].son[0]].sum;//注意最后要加上root的右子树节点数量 
    return ans+1;
}
int arank(int root,int num){
    if(root==0||tree[root].sum<num)
    return 0; 
    if(tree[tree[root].son[0]].sum>=num){//左子树的节点个数大于等于num 
        return arank(tree[root].son[0],num);
    }else if(tree[root].sum-tree[tree[root].son[1]].sum>=num){//前面左子树节点数已经小于num了,假如左子树加当前节点的数量大于等于num,就直接返回当前节点 
        return tree[root].value;
    }else{//否则,向右子树走,但是要加上根节点数量和根节点的左子树大小 
        return arank(tree[root].son[1],num-(tree[root].sum-tree[tree[root].son[1]].sum));
    }
}
int find_pre(int root,int x){
    int now=root,pre=0;//pre保存目前最优解 
    while(now){
        if(tree[now].value<x){//当前节点值小于x,那么更新pre 
            pre=now;
            now=tree[now].son[1];
        }else{
            now=tree[now].son[0];// 如果当前节点的值大于等于x,向左走 
        }
    }
    return tree[pre].value; 
}
int find_suf(int root,int x){
    int now=root,pre=0;//同上,pre记录当前最右值 
    while(now){ 
        if(tree[now].value>x){
            pre=now;
            now=tree[now].son[0];
        }else{
            now=tree[now].son[1];
        }
    }
    return tree[pre].value;
}
int main()
{
    scanf("%d",&n);
    cnt=0;
    int op,x;
    int root=0;
    tree[0].rank=INF;//先把0这个点上的优先级设为无穷大 
    for(int i=0;i<n;i++){
        scanf("%d%d",&op,&x);
        if(op==1){
            insert(root,x);
        }else if(op==2){
            del(root,x);
        }else if(op==3){
            printf("%d
",rank(root,x));
        }else if(op==4){
            printf("%d
",arank(root,x));
        }else if(op==5){
            printf("%d
",find_pre(root,x));
        }else if(op==6){
            printf("%d
",find_suf(root,x));
        }
    }
    return 0;
}
原文地址:https://www.cnblogs.com/6262369sss/p/10816243.html