cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/My/DataStructure/SegmentTree/SparseSegmentTreeGetTest.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../../../Src/DataStructure/SegmentTree/SparseSegmentTree.hpp"

#include <iostream>
#include <vector>
#include <random>
struct M {
    using Element = int;
    static Element identity() {
        return 0;
    }
    static Element operation(Element,Element) {
        return 0;
    }
};

int main() {
    std::mt19937 mt{std::random_device{}()};
    const int size = 10000;
    std::vector<int> a(size, M::identity());
    zawa::SparseSegmentTree<M> seg(size);
    int q = 1000000;
    while (q--) {
        if (mt() % 2) {
            int i = mt() % size;
            assert(a[i] == seg.get(i));
        }
        else {
            int i = mt() % size, v = mt() % 100;
            a[i] = v;
            seg.assign(i, v);
        }
    }
    std::cout << "Hello World\n";
}
#line 1 "Test/My/DataStructure/SegmentTree/SparseSegmentTreeGetTest.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/DataStructure/SegmentTree/SparseSegmentTree.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 5 "Src/DataStructure/SegmentTree/SparseSegmentTree.hpp"

#include <cassert>
#include <limits>
#include <optional>
#include <vector>

namespace zawa {

template <concepts::Monoid Monoid>
class SparseSegmentTree {
public:

    using VM = Monoid;

    using V = typename VM::Element;

    using OM = Monoid;

    using O = typename OM::Element;

    SparseSegmentTree() = default;

    explicit SparseSegmentTree(usize n, usize poolSize = 0u) : m_n{n}, m_pool(1) {
        m_pool.reserve(poolSize);
    }

    inline usize size() const {
        return m_n;
    }

    void assign(usize p, V v) {
        assert(p < size());
        set(0, p, v, 0, size());
    }

    [[nodiscard]] V get(usize p) const {
        return get(0, p, 0, size());
    }

    [[nodiscard]] V operator[](usize p) const {
        return get(0, p, 0, size());
    }

    [[nodiscard]] V product(usize l, usize r) const {
        assert(l <= r and r <= size());
        return product(0, l, r, 0, size());
    }

private:

    struct node {
        static constexpr usize INVALID = std::numeric_limits<usize>::max();
        usize lch{INVALID}, rch{INVALID};
        V v{VM::identity()};
    };

    static constexpr usize mid(usize l, usize r) {
        return (l & r) + ((l ^ r) >> 1);
    }
    
    void set(usize i, usize p, const V& v, usize l, usize r) {
        if (l + 1 == r) {
            m_pool[i].v = v;
            return;
        }
        const usize m = mid(l, r);
        if (p < m) {
            if (m_pool[i].lch == node::INVALID) m_pool[i].lch = makeNode();
            set(m_pool[i].lch, p, v, l, m);
        }
        else {
            if (m_pool[i].rch == node::INVALID) m_pool[i].rch = makeNode();
            set(m_pool[i].rch, p, v, m, r);
        }
        m_pool[i].v = VM::operation(
                m_pool[i].lch == node::INVALID ? VM::identity() : m_pool[m_pool[i].lch].v,
                m_pool[i].rch == node::INVALID ? VM::identity() : m_pool[m_pool[i].rch].v
                );
    }

    V get(usize i, usize p, usize l, usize r) const {
        if (i == node::INVALID) return VM::identity();
        if (l + 1 == r) return m_pool[i].v;
        const usize m = mid(l, r);
        if (p < m) return get(m_pool[i].lch, p, l, m);
        else return get(m_pool[i].rch, p, m, r);
    }

    V product(usize i, usize l, usize r, usize curL, usize curR) const {
        if (i == node::INVALID) return VM::identity();
        if (r <= curL or curR <= l) return VM::identity();
        if (l <= curL and curR <= r) return m_pool[i].v;
        else {
            const usize m = mid(curL, curR);
            return VM::operation(
                        product(m_pool[i].lch, l, r, curL, m),
                        product(m_pool[i].rch, l, r, m, curR)
                    );
        }
    }

    usize makeNode() {
        usize res = m_pool.size();
        m_pool.emplace_back();
        return res;
    }

    usize m_n{};

    std::vector<node> m_pool{};
};

} // namespace zawa
#line 4 "Test/My/DataStructure/SegmentTree/SparseSegmentTreeGetTest.test.cpp"

#include <iostream>
#line 7 "Test/My/DataStructure/SegmentTree/SparseSegmentTreeGetTest.test.cpp"
#include <random>
struct M {
    using Element = int;
    static Element identity() {
        return 0;
    }
    static Element operation(Element,Element) {
        return 0;
    }
};

int main() {
    std::mt19937 mt{std::random_device{}()};
    const int size = 10000;
    std::vector<int> a(size, M::identity());
    zawa::SparseSegmentTree<M> seg(size);
    int q = 1000000;
    while (q--) {
        if (mt() % 2) {
            int i = mt() % size;
            assert(a[i] == seg.get(i));
        }
        else {
            int i = mt() % size, v = mt() % 100;
            a[i] = v;
            seg.assign(i, v);
        }
    }
    std::cout << "Hello World\n";
}
Back to top page