ds/treap_base.hpp

• View this file on GitHub
• Last update: 2025-09-25 11:45:13+07:00
• Include: #include "ds/treap_base.hpp"

Depends on

• ds/bst_base.hpp
• other/st_alloc.hpp

Required by

• Ordered Set (ds/ordered_set.hpp)

Verified with

• test/yosupo/ds/ordered_set.test.cpp
• test/yosupo/ds/point_set_range_frequency.test.cpp

Code

#pragma once

#include "bst_base.hpp"

namespace treap {
    template<class T> using key_t = decltype(declval<T>().key);
    template<class T> struct node : bst::node<T> {
        uint64_t pr = rng();

        static uint64_t rng() {
            static mt19937_64 mt(
                chrono::steady_clock::now().time_since_epoch().count());
            return mt();
        }
    };

    template<class T> T *merge(node<T> *_l, node<T> *_r) {
        T *l = (T *)_l, *r = (T *)_r;
        if (!l || !r) return l ? l : r;
        if (l->pr > r->pr) {
            l->r = merge(l->r, r), l->pull();
            return l;
        } else {
            r->l = merge(l, r->l), r->pull();
            return r;
        }
    }
    template<class T>
    pair<T *, T *> split(node<T> *_t, const key_t<T> &k, bool include = true) {
        T *t = (T *)_t;
        if (!t) return {nullptr, nullptr};
        if (k < t->key || (k == t->key && !include)) {
            auto s = split(t->l, k, include);
            t->l = s.second, t->pull();
            return {s.first, t};
        } else {
            auto s = split(t->r, k, include);
            t->r = s.first, t->pull();
            return {t, s.second};
        }
    }
} // namespace treap

#line 2 "ds/treap_base.hpp"

#line 2 "ds/bst_base.hpp"

#line 2 "other/st_alloc.hpp"

template<class T> struct st_alloc {
    static inline stack<T> pool;
    void *operator new(size_t) { return pool.emplace(), &pool.top(); }
    void operator delete(void *) {}
};
#line 4 "ds/bst_base.hpp"

namespace bst {
    template<class T> struct node : st_alloc<T> {
        T *l = nullptr, *r = nullptr;
        void pull() { ((T *)this)->_pull(); }
    };
} // namespace bst
#line 4 "ds/treap_base.hpp"

namespace treap {
    template<class T> using key_t = decltype(declval<T>().key);
    template<class T> struct node : bst::node<T> {
        uint64_t pr = rng();

        static uint64_t rng() {
            static mt19937_64 mt(
                chrono::steady_clock::now().time_since_epoch().count());
            return mt();
        }
    };

    template<class T> T *merge(node<T> *_l, node<T> *_r) {
        T *l = (T *)_l, *r = (T *)_r;
        if (!l || !r) return l ? l : r;
        if (l->pr > r->pr) {
            l->r = merge(l->r, r), l->pull();
            return l;
        } else {
            r->l = merge(l, r->l), r->pull();
            return r;
        }
    }
    template<class T>
    pair<T *, T *> split(node<T> *_t, const key_t<T> &k, bool include = true) {
        T *t = (T *)_t;
        if (!t) return {nullptr, nullptr};
        if (k < t->key || (k == t->key && !include)) {
            auto s = split(t->l, k, include);
            t->l = s.second, t->pull();
            return {s.first, t};
        } else {
            auto s = split(t->r, k, include);
            t->r = s.first, t->pull();
            return {t, s.second};
        }
    }
} // namespace treap

Back to top page