2 条题解

  • 1
    @ 2022-9-6 14:51:42

    标准Treap树:

    #include <bits/stdc++.h>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

struct Node
{
    int l, r;
    int cnt;
    int val;
    int key;
    int size;
}tr[N];

int root, idx;

void pushup(int p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}

int get_node(int key)
{
    idx++;
    tr[idx].val = rand();
    tr[idx].key = key;
    tr[idx].size = tr[idx].cnt = 1;
    return idx;
}

void zig(int& p)                //右旋
{
    int q = tr[p].l;
    tr[p].l = tr[q].r;
    tr[q].r = p;
    p = q;
    pushup(p);
    pushup(tr[p].r);
}

void zag(int& p)                //左旋
{
    int q = tr[p].r;
    tr[p].r = tr[q].l;
    tr[q].l = p;
    p = q;
    pushup(p);
    pushup(tr[p].l);
}

void build()
{
    root = get_node(-INF);
    tr[root].r = get_node(INF);
    if (tr[root].val < tr[tr[root].r].val)zag(root);
}

void insert(int& p, int key)
{
    if (!p)p = get_node(key);
    else if (tr[p].key == key)tr[p].cnt++;
    else if (tr[p].key < key)
    {
        insert(tr[p].r, key);
        if (tr[p].val < tr[tr[p].r].val)zag(p);
    }
    else
    {
        insert(tr[p].l, key);
        if (tr[p].val < tr[tr[p].l].val)zig(p);
    }
    pushup(p);
}

void remove(int& p, int key)
{
    if (!p)return;
    if (tr[p].key == key)
    {
        if (tr[p].cnt > 1)tr[p].cnt--;
        else if (tr[p].l || tr[p].r)
        {
            if (!tr[p].r || tr[tr[p].r].val < tr[tr[p].l].val)
            {
                zig(p);
                remove(tr[p].r, key);
            }
            else
            {
                zag(p);
                remove(tr[p].l, key);
            }
        }
        else p = 0;
    }
    else if (tr[p].key < key)remove(tr[p].r, key);
    else remove(tr[p].l, key);
    pushup(p);
}

int get_rank_by_key(int p, int key)
{
    if (!p)return INF;
    if (tr[p].key == key)return tr[tr[p].l].size + 1;
    else if (tr[p].key <= key)return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
    return get_rank_by_key(tr[p].l, key);
}

int get_key_by_rank(int p, int rank)
{
    if (!p)return INF;
    if (rank <= tr[tr[p].l].size)return get_key_by_rank(tr[p].l, rank);
    else if (rank <= tr[tr[p].l].size + tr[p].cnt)return tr[p].key;
    else return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int n;

int get_prev(int p, int key)
{
    if (!p)return -INF;
    if (tr[p].key >= key)return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key)
{
    if (!p)return INF;
    if (tr[p].key <= key)return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();
    scanf("%d", &n);
    while (n--)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        switch (op)
        {
        case 1:
            insert(root, x);
            break;
        case 2:
            remove(root, x);
            break;
        case 3:
            printf("%d\n", get_rank_by_key(root, x) - 1);
            break;
        case 4:
            printf("%d\n", get_key_by_rank(root, x + 1));
            break;
        case 5:
            printf("%d\n", get_prev(root, x));
            break;
        case 6:
            printf("%d\n", get_next(root, x));
            break;
        }
    }
    return 0;
}
    • 0
      @ 2022-11-24 21:11:59

      Treap

      Treap（Tree+Heap），中文名 树堆，为一种二叉搜索树。

      Treap 的每个节点至少有两个值，一个值为数值，满足二叉查找树性质；另一个值为权值，满足堆的性质。

      在实际应用中，Treap 有两种：有旋 Treap 和无旋 Treap。

      有旋 Treap

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp = std::less<_Tp> >
class rotate_treap {
    Node<_Tp, _UIntType> *root;
    _KeyOfValue _key_of_value;
    _Comp _comp;
public:
    inline void insert_unique(const _Tp& v);
    inline void insert_equal(const _Tp& v);
    inline void erase(const _Tp& v);
    inline _Tp lower_bound(const _Tp& v) const;
    inline _Tp upper_bound(const _Tp& v) const;
    inline std::size_t Rank(const _Tp& v) const;
    inline const _Tp operator[](std::size_t index) const;
    std::pair<_Tp, _Tp> equal_range(const _Tp& v) const;
};

      旋转

      旋转的概念已于 WBLT 一文提到过。在此再说一下：

      • 左旋（left rotate 或 zag）
      • 右旋（right rotate 或 zig）

      这些概念会在关于平衡树的文章中多次出现。

      设这张图为 左：

      设这张图为 右：

      在 左 图中将树绕 2 右旋便得到了 右 图；

      在 右 图中将树绕 4 左旋便得到了 左 图。

      template <typename _Tp, typename _UIntType>
class Node {
public:
    size_t size;
    _Tp value;
    size_t cnt;
    _UIntType priority;
    Node *left, *right;
    Node(size_t s = 0, const _Tp &v = _Tp(), size_t c = 0, const _UIntType &pro = _UIntType(), Node *l = nullptr, Node *r = nullptr)
        : size(s), value(v), cnt(c), priority(pro), left(l), right(r) {}
    ~Node() = default;
    Node<_Tp, _UIntType> &operator=(const Node<_Tp, _UIntType>& o) {
        size = o.size;
        value = o.value;
        cnt = o.cnt;
        priority = o.priority;
        left = o.left;
        right = o.right;
        return *this;
    }
    inline void update() {
        size = cnt;
        if (!my_is_nullptr(left)) size += left->size;
        if (!my_is_nullptr(right)) size += right->size;
    }
};
template <typename _Tp, typename _UIntType>
inline void zig(Node<_Tp, _UIntType> *& cur) { // 图中为指向 3 的节点
    /******************
     * cur:
     *       4
     *   2       5
     * 1   3
     ******************/
    Node<_Tp, _UIntType> * tmp = cur->left;
    /******************
     * tmp:
     *   2
     * 1   3
     ******************/
    cur->left = tmp->right;
    /******************
     * cur:
     *       4
     *   3       5
     ******************/
    /******************
     * tmp:
     *   2
     * 1   3
     ******************/
    tmp->right = cur;
    /******************
     * cur:
     *       4
     *   3       5
     ******************/
    /******************
     * tmp:
     *     2 
     * 1       4
     *       3   5
     ******************/
    tmp->update();
    cur->update(); // 更新
    cur = tmp;
}
template <typename _Tp, typename _UIntType>
inline void zag(Node<_Tp, _UIntType> *& cur) {
    Node<_Tp, _UIntType> * tmp = cur->right;
    cur->right = tmp->left;
    tmp->left = cur;
    tmp->update();
    cur->update();
    cur = tmp;
}

      插入

      与普通的二叉查找树一样，但是注意需要通过旋转平衡。

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp = std::less<_Tp> >
void __insert_unique(Node<_Tp, _UIntType> *& cur, const _Tp& v, _KeyOfValue key_of_value, _Comp comp) {
    if (my_is_nullptr(cur)) {
        cur = new Node<_Tp, _UIntType>(1, v, 1, rd(), nullptr, nullptr);
        return;
    }
    if (!comp(key_of_value(cur->value), key_of_value(v)) && !comp(key_of_value(v), key_of_value(cur->value))) { // key_of_value(cur->value) == key_of_value(v)
        return;
    }
    if (comp(key_of_value(v), key_of_value(cur->value))) {
        __insert_unique(cur->left, v, key_of_value, comp);
        if (cur->left->priority < cur->priority) {
            zig(cur);
        }
    }
    else {
        __insert_unique(cur->right, v, key_of_value, comp);
        if (cur->right->priority < cur->priority) {
            zag(cur);
        }
    }
    cur->update();
    return;
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp = std::less<_Tp> >
void __insert_equal(Node<_Tp, _UIntType> *& cur, const _Tp& v, _KeyOfValue key_of_value, _Comp comp) {
    if (my_is_nullptr(cur)) {
        cur = new Node<_Tp, _UIntType>(1, v, 1, rd(), nullptr, nullptr);
        return;
    }
    if (!comp(key_of_value(cur->value), key_of_value(v)) && !comp(key_of_value(v), key_of_value(cur->value))) { // key_of_value(cur->value) == key_of_value(v)
        ++cur->cnt;
        ++cur->size;
        return;
    }
    if (comp(key_of_value(v), key_of_value(cur->value))) {
        __insert_unique(cur->left, v, key_of_value, comp);
        if (cur->left->priority < cur->priority) {
            zig(cur);
        }
    }
    else {
        __insert_unique(cur->right, v, key_of_value, comp);
        if (cur->right->priority < cur->priority) {
            zag(cur);
        }
    }
    cur->update();
    return;
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline void rotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::insert_unique(const _Tp& v) {
    __insert_unique(root, v, _key_of_value, _comp);
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline void rotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::insert_equal(const _Tp& v) {
    __insert_equal(root, v, _key_of_value, _comp);
}

      删除

      也没什么区别，就是要维护树中的堆，使其保持一个小根堆的状态。

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
void __erase(Node<_Tp, _UIntType> *& cur, const _Tp& v, _KeyOfValue key_of_value, _Comp comp) {
    if (my_is_nullptr(cur)) return;
    if (comp(key_of_value(v), key_of_value(cur->value))) {
        __erase(cur->left, v, key_of_value, comp);
        cur->update();
    }
    else if (comp(key_of_value(cur->value), key_of_value(v))) {
        __erase(cur->right, v, key_of_value, comp);
        cur->update();
	}
    else { // key_of_value(cur->value) == key_of_value(v)
        if (cur->cnt > 1) {
            --cur->cnt;
            --cur->size;
            return;
        }
        short state = 0;
        state |= (!my_is_nullptr(cur->left));
        state |= (!my_is_nullptr(cur->right) << 1);
        Node<_Tp, _UIntType> *tmp = cur;
        switch (state) {
            case 0: {
                delete cur;
                cur = nullptr;
                break;
            }
            case 1: {
                cur = tmp->left;
                delete tmp;
                break;
            }
            case 2: {
                cur = tmp->right;
                delete tmp;
                break;
            }
            default: {
                if (cur->left->priority < cur->right->priority) {
                    zig(cur);
                    __erase(cur->right, v, key_of_value, comp);
                }
                else {
                    zag(cur);
                    __erase(cur->left, v, key_of_value, comp);
                }
                cur->update();
            }
        }
    }
    return;
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline void rotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
erase(const _Tp& v) {
    __erase(root, v, _key_of_value, _comp);
}

      查询第 index 个值

      template <typename _Tp, typename _UIntType>
const _Tp __how_much(Node<_Tp, _UIntType> * cur, size_t index) {
    size_t less_siz = my_is_nullptr(cur->left) ? 0 : cur->left->size;
    if (index <= less_siz) {
        return __how_much(cur->left, index);
    }
    if (index <= less_siz + cur->cnt) {
        return cur->value;
    }
    return __how_much(cur->right, index - less_siz - cur->cnt);
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline const _Tp rotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
operator[](size_t index) const {
    return __how_much(root, index);
}

      查询排名

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
size_t __rank(Node<_Tp, _UIntType> * cur, const _Tp& v, _KeyOfValue key_of_value, _Comp comp) {
    size_t less_siz = my_is_nullptr(cur->left) ? 0 : cur->left->size;
    if (comp(key_of_value(v), key_of_value(cur->value))) {
        if (!my_is_nullptr(cur->left)) return __rank(cur->left, v, key_of_value, comp);
        return 1;
    }
    if (comp(key_of_value(cur->value), key_of_value(v))) {
        if (!my_is_nullptr(cur->right)) return less_siz + cur->cnt + __rank(cur->right, v, key_of_value, comp);
        return cur->size + 1;
    }
    return less_siz + 1;
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
size_t rotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
Rank(const _Tp& v) const {
    return __rank(root, v, _key_of_value, _comp);
}

      lower_bound 和 upper_bound

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline _Tp rotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
lower_bound(const _Tp& v) const {
    return this->operator[](Rank(v));
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline _Tp rotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
upper_bound(const _Tp& v) const {
    return this->operator[](Rank(v) + 1);
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp = std::less<_Tp> >
inline std::pair<_Tp, _Tp> rotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
equal_range(const _Tp& v) {
    return std::make_pair(lower_bound(v), upper_bound(v));
}

      无旋 Treap

      才讲到啊。

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp = std::less<_Tp> >
class nrotate_treap {
    Node<_Tp, _UIntType>* root;
    _KeyOfValue _key_of_value;
    _Comp comp;
    static void split(Node<_Tp, _UIntType> * cur, _Tp v, Node<_Tp, _UIntType> *& l, Node<_Tp, _UIntType> *& r, _KeyOfValue key_of_value, _Comp comp);
    static Node<_Tp, _UIntType> * merge(Node<_Tp, _UIntType> * l, Node<_Tp, _UIntType> * r);
public:
    inline void insert_unique(const _Tp& v);
    inline void insert_equal(const _Tp& v);
    inline void erase(const _Tp& v);
    inline _Tp lower_bound(const _Tp& v) const;
    inline _Tp upper_bound(const _Tp& v) const;
    inline std::size_t Rank(const _Tp& v) const;
    inline const _Tp operator[](std::size_t index) const;
    inline std::pair<_Tp, _Tp> equal_range(const _Tp& v) const;
};

      只有两种核心操作：分裂（split）和 合并（merge）。

      分裂

      这张图为分裂前的图片。

      xfRpWV.png

      这张图为按照 3 分裂后的第一棵树。

      xfR9zT.png

      这张图为按照 3 分裂后的第二棵树。

      xfRSJ0.png

      在经过一轮 合并 操作后会变成分裂前的样子。

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
void nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
split(Node<_Tp, _UIntType> * cur, _Tp v, Node<_Tp, _UIntType> *& l, Node<_Tp, _UIntType> *& r, _KeyOfValue key_of_value, _Comp comp) {
    if (!cur) {
        l = r = nullptr;
        return;
    }
    if (comp(key_of_value(v), key_of_value(cur->value))) {
        split(cur->left, v, l, cur->left, key_of_value, comp);
        cur->update();
        r = cur;
    }
    else {
        split(cur->right, v, cur->right, r, key_of_value, comp);
        cur->update();
        l = cur;
    }
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
Node<_Tp, _UIntType> * nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
merge(Node<_Tp, _UIntType> * l, Node<_Tp, _UIntType> * r) {
    if (!l) return r;
    if (!r) return l;
    if (l->priority < r->priority) {
        l->right = merge(l->right, r);
        l->update();
        return l;
    }
    r->left = merge(l, r->left);
    r->update();
    return r;
}

      背下来就好。

      插入

      一样。

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline void nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
insert_unique(const _Tp& v) {
    Node<_Tp, _UIntType> * l, * tmp, * r;
    split(root, v, l, r);
    split(l, v - 1, l, tmp);
    if (my_is_nullptr(tmp)) {
        tmp = new Node<_Tp, _UIntType>(1, v, 1, rand(), nullptr, nullptr);
    }
    root = merge(merge(l, tmp), r);
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline void nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
insert_equal(const _Tp& v) {
    Node<_Tp, _UIntType> * l, * tmp, * r;
    split(root, v, l, r, _key_of_value, comp);
    split(l, v - 1, l, tmp, _key_of_value, comp);
    if (my_is_nullptr(tmp)) {
        tmp = new Node<_Tp, _UIntType>(1, v, 1, rand(), nullptr, nullptr);
    }
    else {
        ++tmp->cnt;
        ++tmp->size;
    }
    root = merge(merge(l, tmp), r);
}

      删除

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline void nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
erase(const _Tp& v) {
    Node<_Tp, _UIntType> * l, * tmp, * r;
    split(root, v, l, r, _key_of_value, comp);
    split(l, v - 1, l, tmp, _key_of_value, comp);
    if (my_is_nullptr(tmp)) {
        root = merge(l, r);
        return;
    }
    if (tmp->cnt > 1) {
        --tmp->cnt;
        --tmp->size;
        root = merge(merge(l, tmp), r);
        return;
    }
    // tmp->cnt == 1
    tmp = merge(tmp->left, tmp->right);
    root = merge(merge(l, tmp), r);
    return;
}

      查询第 index 个数

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline const _Tp nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
operator[](size_t index) const {
    Node<_Tp, _UIntType> * u = root;
    while (!my_is_nullptr(u)) {
        size_t left_siz = my_is_nullptr(u->left) ? 0 : u->left->size;
        if (left_siz + 1 == index) break;
        if (left_siz + 1 < index) {
            index -= left_siz + u->cnt;
            u = u->right;
        }
        else {
            u = u->left;
        }
    }
    return u->value;
}

      查询 val 的排名

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline size_t nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
Rank(const _Tp& v) {
    Node<_Tp, _UIntType> * x, * y;
    split(root, v - 1, x, y, _key_of_value, comp);
    size_t res = (my_is_nullptr(x) ? 0 : x->size) + 1;
    root = merge(x, y);
    return res;
}

      lower_bound 和 upper_bound

      template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline _Tp nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
lower_bound(const _Tp& v) {
    return this->operator[](Rank(v));
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline _Tp nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
upper_bound(const _Tp& v) {
    return this->operator[](Rank(v) + 1);
}
template <typename _Tp, typename _UIntType, typename _KeyOfValue, typename _Comp>
inline std::pair<_Tp, _Tp> nrotate_treap<_Tp, _UIntType, _KeyOfValue, _Comp>::
equal_range(const _Tp& v) {
    return std::make_pair(lower_bound(v), upper_bound(v));
}

      代码前面放了，这里就不汇总了。

      文艺平衡树

      在结构体中修改变量，添加一个 revtag，然后把 Treap 做成一种类似于动态开点线段树的数据结构就可以了。

      template <typename _Tp, typename _UIntType>
class Node {
public:
    size_t size, cnt;
    _Tp value;
    _UIntType priority;
    bool tag;
    Node<_Tp, _UIntType> *left, *right;
    inline Node(size_t s = 1, size_t c = 1, const _Tp& v = _Tp(), const _UIntType& pri = _UIntType(), bool tg = false, Node<_Tp, _UIntType>* l = nullptr, Node<_Tp, _UIntType>* r = nullptr) : size(s), cnt(c), value(v), priority(pri), tag(tg), left(l), right(r) {}
    inline ~Node() = default;
    template <typename _Ostream>
    friend _Ostream& operator<<(_Ostream& os, Node<_Tp, _UIntType>* cur) {
        if (my_is_nullptr(cur)) return os;
        cur->pushdown();
        os << cur->left;
        os << cur->value << ' ';
        os << cur->right;
        return os;
    }
    inline void pushdown() {
        if (tag) {
            std::swap(left, right);
            if (!my_is_nullptr(left)) left->tag ^= 1;
            if (!my_is_nullptr(right)) right->tag ^= 1;
            tag = false;
        }
    }
    inline void update() {
        size = cnt;
        if (!my_is_nullptr(left)) size += left->size;
        if (!my_is_nullptr(right)) size += right->size;
    }
};
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
class segment_nrotate_treap {
    typedef typename _Rand::result_type _UIntType;
    typedef Node<_Tp, _UIntType>* node_type;
    _KeyOfValue _M_key_of_value;
    _Comp _M_comp;
    node_type _M_root;
    _Rand rd;
    std::less<_UIntType> _M_priority_comp;
    static inline void split(Node<_Tp, _UIntType> *cur, _Tp v, Node<_Tp, _UIntType> *&l, Node<_Tp, _UIntType> *&r, _KeyOfValue key_of_value, _Comp comp);
    static inline void split_by_rank(Node<_Tp, _UIntType>* cur, size_t rk, Node<_Tp, _UIntType> *&l, Node<_Tp, _UIntType> *&r);
    template <typename _Priority_comp>
    static inline Node<_Tp, _UIntType> *merge(Node<_Tp, _UIntType> *l, Node<_Tp, _UIntType> *r, _Priority_comp comp);
public:
    inline segment_nrotate_treap() = default;
    inline void reverse(size_t l, size_t r) {
        node_type left = nullptr, mid = nullptr, right = nullptr;
        split_by_rank(_M_root, r, mid, right);
        split_by_rank(mid, l - 1, left, mid);
        if (!my_is_nullptr(mid)) {
            mid->tag = true;
            mid->pushdown();
        }
        _M_root = merge(left, merge(mid, right, _M_priority_comp), _M_priority_comp);
        if (!my_is_nullptr(_M_root)) _M_root->update();
    }
    inline void insert_equal(const _Tp& value) {
        if (my_is_nullptr(_M_root)) {
            _M_root = new Node<_Tp, _UIntType>(1, 1, value, rd(), false, nullptr, nullptr);
            return;
        }
        node_type l = nullptr, mid = nullptr, r = nullptr;
        split(_M_root, value, l, r, _M_key_of_value, _M_comp);
        split(l, value - 1, l, mid, _M_key_of_value, _M_comp);
        if (my_is_nullptr(mid)) mid = new Node<_Tp, _UIntType>(1, 1, value, rd(), false, nullptr, nullptr);
        else {
            ++mid->cnt;
            ++mid->size;
        }
        _M_root = merge(l, merge(mid, r, _M_priority_comp), _M_priority_comp);
        if (!my_is_nullptr(_M_root)) _M_root->update();
    }
    template <typename _Ostream>
    friend _Ostream& operator<<(_Ostream& os, segment_nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp> o) { return os << o._M_root; }
};
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
inline void segment_nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::split(Node<_Tp, typename _Rand::result_type> *cur, _Tp v, Node<_Tp, typename _Rand::result_type> *&l, Node<_Tp, typename _Rand::result_type> *&r, _KeyOfValue key_of_value, _Comp comp) {
    if (my_is_nullptr(cur)) {
        l = r = nullptr;
        return;
    }
    if (comp(key_of_value(v), key_of_value(cur->value))) {
        split(cur->left, v, l, cur->left, key_of_value, comp);
        cur->update();
        r = cur;
    }
    else {
        split(cur->right, v, cur->right, r, key_of_value, comp);
        cur->update();
        l = cur;
    }
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
void segment_nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::split_by_rank(Node<_Tp, _UIntType>* cur, size_t rk, Node<_Tp, _UIntType> *&l, Node<_Tp, _UIntType> *&r) {
    if (my_is_nullptr(cur)) {
        l = r = nullptr;
        return;
    }
    cur->pushdown();
    size_t ls_siz = my_is_nullptr(cur->left) ? 0 : cur->left->size;
    if (rk <= ls_siz) {
        r = cur;
        r->pushdown();
        r->update();
        split_by_rank(r->left, rk, l, r->left);
        cur->update();
        cur->pushdown();
        return;
    }
    l = cur;
    l->pushdown();
    l->update();
    split_by_rank(l->right, rk - ls_siz - 1, l->right, r);
    cur->update();
    cur->pushdown();
    return;
}
template <typename _Tp, typename _Rand, typename _KeyOfValue, typename _Comp>
template <typename _Priority_comp>
Node<_Tp, typename _Rand::result_type> *segment_nrotate_treap<_Tp, _Rand, _KeyOfValue, _Comp>::merge(Node<_Tp, typename _Rand::result_type> *l, Node<_Tp, typename _Rand::result_type> *r, _Priority_comp comp) {
    if (my_is_nullptr(l)) return r;
    if (my_is_nullptr(r)) return l;
    l->pushdown();
    r->pushdown();
    if (comp(l->priority, r->priority)) {
        l->pushdown();
        l->right = merge(l->right, r, comp);
        l->update();
        return l;
    }
    r->pushdown();
    r->left = merge(l, r->left, comp);
    r->update();
    return r;
}

      练习：

      1. 【模板】普通平衡树
      2. 【模板】普通平衡树（加强版）
      3. 【模板】文艺平衡树
      4. [SCOI2010]序列操作
      5. [NOI2003]文本编辑器
      6. [ZHOI2006]文本编辑器
      7. 由乃与大母神原型和偶像崇拜
      8. [Ynoi2014]人人本着正义之名
      • 1

      【模板】普通平衡树

      信息

      ID
      2305
      时间
      1000ms
      内存
      128MiB
      难度
      5
      标签
      递交数
      148
      已通过
      25
      上传者
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. 兼容模式
      8. 主题
      2. © 2021-2024 Hydro.ac
      4. Worker 0 in 45ms
      5. Hydro v4.11.2 Professional