刚刚跟着EM-LGH大佬学了非旋转Treap

非常庆幸不用再写万恶的rotate了（来自高级数据结构的恶意）

来记一下

Treap

概念

简单来说，$Tree_{二叉搜索树} * Heap_堆 = Treap_{平衡树}$

这显然不是袁隆平爷爷干的

二叉搜索树，堆←不懂请戳这里

显然这两样东西有各自的排列顺序——左小右大以及根小（大）儿子大（小）

对于寻找答案来讲，二叉搜索树更加方便

— 那么堆用来干嘛呢

很简单，用来达到期望平衡

— 怎么实现呢

通过另一个关键字

— 为什么是“期望”平衡呢

因为是通过随机的关键字啊！

操作

上面说过了，二叉搜索树管答案，堆管时间

李云龙：“你管生活，我管军事”

如何让随机的关键字满足堆的性质，同时节点的值满足二叉搜索树的性质呢

旋转

然而这个玩意十分难写且难理解。。。

所以就出现了……

非旋转Treap

它与旋转的Treap很相似

但是它是基于分裂和合并两个基本操作而不是旋转

-define表+struct，请对照此表理解代码-

#define lson t[x].ls

#define rson t[x].rs

#define si t[x].size

#define ra t[x].ran

#define lss t[t[x].ls].size

#define rss t[t[x].rs].size

#define va t[x].val

//-------------------------

struct node

{

    int val, size, ls, rs, ran;

}t[100001];

新建节点

正常的初始化

inline void newnode(int &x, int val)

{

    ++tot;

    t[tot].size=1;

    t[tot].val=val;

    t[tot].ran=rand();

    t[tot].ls=t[tot].rs=0;

    x=tot;

}

分裂

指定一个val，将值∈[0, val]的节点与值∈(val, +∞)的节点分成两棵树

实现过程和寻找后继的过程很像

void split(int x, int &l, int &r, int val)

{

    if(!x)

    {

        l = r = 0;

        return;

    }

    if(va <= val) l = x, split(t[x].rs, t[l].rs, r, val);//当前值比val小或等于val，则将它与它的左子树全部划分到第一棵树，继续寻找它的右子树

    else r = x, split(t[x].ls, l, t[r].ls, val);//反之，则将它与它的右子树划分到第二棵树，寻找它的左子树

    pushup(x);//不要忘记更新size

}

合并

分裂的反过程

要求合并的A树与B树中$A_{max} < B_{min}$

void merge(int &x, int a, int b)

{

    if(!a||!b)

    {

        x = a + b;

        return;

    }

    if(t[a].ran < t[b].ran) x = a, merge(t[x].rs, t[a].rs, b);//随机值在这里用，用来在合并时维护堆的性质

    else x = b, merge(t[x].ls, a, t[b].ls);

    pushup(x);//更新！

}

插入

基于分裂和合并

在$val - 1$处分裂->合并节点Z与树A->合并树A与树B

void insert(int val)

{

    int x = 0, y = 0, z = 0;

    newnode(z, val);

    split(root, x, y, val - 1);

    merge(x, x, z);

    merge(root, x, y);

}

删除

和插入很像

将大树在$val - 1$处分裂成AB->将树B在$val$处分裂成BC->合并树A与树C

void del(int val)

{

    int x = 0, y = 0, z = 0;

    split(root, x, y, val);

    split(x, x, z, val - 1);

    merge(z, t[z].ls, t[z].rs);//这里是只删除一个的操作，全部删除请忽略本行和下一行

    merge(x, x, z);

    merge(root, x, y);

}

询问排名

和插入很像

在$val-1$处分裂->输出A的size

void ask_rank(int v)

{

    int x = 0, y = 0;

    split(root, x, y, v - 1);

    cout << si + 1;

    merge(root, x, y);

}

询问第k小

相当于反着问排名

void ask_num(int x, int kth)

{

    while(lss + 1 != kth)

    {

        if(lss >= kth) x = lson;

        else kth -= (lss + 1), x = rson;

    }

    cout << va;

}

前驱

在$v-1$处分裂->询问A中最大（第size小）->合并

void ask_fr(int v)

{

    int x = 0, y = 0;

    split(root, x, y, v - 1);

    ask_num(x, si);

    merge(root, x, y);

}

后继

与前驱相反

在$v$处分裂->询问B中第一小->合并

void ask_ba(int v)

{

    int x = 0, y = 0;

    split(root, x, y, v);

    ask_num(y, 1);

    merge(root, x, y);

}

时间复杂度

由于它是期望平衡的，所以它的所有操作都在$O(logN)$左右。

总代码（以Luogu P3369为例）

#include <bits/stdc++.h>

#define lson t[x].ls

#define rson t[x].rs

#define si t[x].size

#define ra t[x].ran

#define lss t[t[x].ls].size

#define rss t[t[x].rs].size

#define va t[x].val

using namespace std;

int root;

namespace treap

{

    int tot;

    struct node

    {

        int val, size, ls, rs, ran;

    }t[100001];

    inline void newnode(int &x, int val)

    {

        ++tot;

        t[tot].size=1;

        t[tot].val=val;

        t[tot].ran=rand();

        t[tot].ls=t[tot].rs=0;

        x=tot;

    }

    inline void pushup(int x)

    {

        si = lss + rss + 1;

    }

    void split(int x, int &l, int &r, int val)

    {

        if(!x)

        {

            l = r = 0;

            return;

        }

        if(va <= val) l = x, split(t[x].rs, t[l].rs, r, val);

        else r = x, split(t[x].ls, l, t[r].ls, val);

        pushup(x);

    }

    void merge(int &x, int a, int b)

    {

        if(!a||!b)

        {

            x = a + b;

            return;

        }

        if(t[a].ran < t[b].ran) x = a, merge(t[x].rs, t[a].rs, b);

        else x = b, merge(t[x].ls, a, t[b].ls);

        pushup(x);

    }

    void insert(int val)

    {

        int x = 0, y = 0, z = 0;

        newnode(z, val);

        split(root, x, y, val - 1);

        merge(x, x, z);

        merge(root, x, y);

    }

    void del(int val)

    {

        int x = 0, y = 0, z = 0;

        split(root, x, y, val);

        split(x, x, z, val - 1);

        merge(z, t[z].ls, t[z].rs);

        merge(x, x, z);

        merge(root, x, y);

    }

    void ask_rank(int v)

    {

        int x = 0, y = 0;

        split(root, x, y, v - 1);

        cout << si + 1;

        merge(root, x, y);

    }

    void ask_num(int x, int kth)

    {

        while(lss + 1 != kth)

        {

            if(lss >= kth) x = lson;

            else kth -= (lss + 1), x = rson;

        }

        cout << va;

    }

    void ask_fr(int v)

    {

        int x = 0, y = 0;

        split(root, x, y, v - 1);

        ask_num(x, si);

        merge(root, x, y);

    }

    void ask_ba(int v)

    {

        int x = 0, y = 0;

        split(root, x, y, v);

        ask_num(y, 1);

        merge(root, x, y);

    }

};

using namespace treap;

int main()

{

    int n;

    cin >> n;

    srand(2005);

    while(n--)

    {

        int x, y;

        cin >> x >> y;

        if(x == 1) insert(y);

        else if(x == 2) del(y);

        else if(x == 3) ask_rank(y), cout << endl;

        else if(x == 4) ask_num(root, y), cout << endl;

        else if(x == 5) ask_fr(y), cout << endl;

        else if(x == 6) ask_ba(y), cout << endl;

    }

    return 0;

}

完结，撒花！！！！！！！★,°:.☆(￣▽￣)/$:.°★ 。

巴特西

关于非旋转Treap