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/AOJ/DSL_2_D.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_D"

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

#include <cassert>
#include <iostream>
#include <vector>

using namespace zawa;

struct M {
    using Element = int;
    static int identity() {
        return -1;
    }
    static int operation(int a, int b) {
        return (b == identity() ? a : b);
    }
};

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n, q; std::cin >> n >> q;
    DualSegmentTree<M> seg(std::vector<int>(n, (1LL << 31) - 1));
    while (q--) {
        int t; std::cin >> t;
        if (t == 0) {
            int l, r, x; std::cin >> l >> r >> x;
            seg.operation(l, r + 1, x);
        }
        else if (t == 1) {
            int i; std::cin >> i;
            std::cout << seg[i] << '\n';
        }
        else {
            assert(false);
        }
    }
}
#line 1 "Test/AOJ/DSL_2_D.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_D"

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

#line 2 "Src/DataStructure/SegmentTree/CommutativeDualSegmentTree.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/CommutativeDualSegmentTree.hpp"

#include <bit>
#include <cassert>
#include <vector>
#include <iterator>
#include <ostream>

namespace zawa {

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

    using OM = Monoid;

    using O = typename OM::Element;

    using VM = Monoid;

    using V = typename VM::Element;

    CommutativeDualSegmentTree() = default;

    explicit CommutativeDualSegmentTree(usize n) 
        : m_n{ n }, m_dat((n << 1), VM::identity()) {}

    explicit CommutativeDualSegmentTree(const std::vector<O>& dat) 
        : m_n{ dat.size() }, m_dat((m_n << 1), VM::identity()) {
        initDat(dat.begin(), dat.end());
    }

    template <class InputIterator>
    CommutativeDualSegmentTree(InputIterator first, InputIterator last)
        : m_n{ static_cast<usize>(std::distance(first, last)) }, m_dat((m_n << 1), OM::identity()) {
        initDat(first, last);
    }

    [[nodiscard]] inline usize size() const noexcept {
        return m_n;
    }

    virtual void operation(usize l, usize r, const O& v) {
        assert(l <= r and r <= size());
        for (l += size(), r += size() ; l < r ; l = parent(l), r = parent(r)) {
            if (l & 1) {
                m_dat[l] = OM::operation(m_dat[l], v);
                l++;
            }
            if (r & 1) {
                r--;
                m_dat[r] = OM::operation(m_dat[r], v);
            }
        }
    }

    // 未verify
    virtual void operation(usize i, const O& o) {
        assert(i < size());
        m_dat[i + size()] = OM::operation(m_dat[i + size()], o);
    }

    void assign(usize i, const V& v) {
        assert(i < size());
        push(i);
        m_dat[i + size()] = v;
    }

    [[nodiscard]] virtual V operator[](usize i) {
        assert(i < size());
        V res{ VM::identity() };
        for (i += size() ; i ; i = parent(i)) {
            res = VM::operation(res, m_dat[i]);
        }
        return res;
    }

    friend std::ostream& operator<<(std::ostream& os, const CommutativeDualSegmentTree seg) {
        usize size{ seg.m_dat.size() };
        for (usize i{1} ; i < size ; i++) {
            os << seg.m_dat[i] << (i + 1 == size ? "" : " ");
        }
        return os;
    }

protected:

    static constexpr usize parent(usize v) noexcept {
        return v >> 1;
    }

    static constexpr usize left(usize v) noexcept {
        return v << 1;
    }

    static constexpr usize right(usize v) noexcept {
        return v << 1 | 1;
    }

    usize m_n;

    std::vector<V> m_dat;

    template <class InputIterator>
    inline void initDat(InputIterator first, InputIterator last) {
        for (auto it{ first } ; it != last ; it++) {
            m_dat[size() + std::distance(first, it)] = *it;
        }
    }

    void push(usize i) {
        assert(i < size());
        i += size();
        usize height{ 64u - std::countl_zero(i) };
        for (usize h{ height } ; --h ; ) {
            usize v{ i >> h };
            m_dat[left(v)] = OM::operation(m_dat[left(v)], m_dat[v]);
            m_dat[right(v)] = OM::operation(m_dat[right(v)], m_dat[v]);
            m_dat[v] = OM::identity();
        }
    }

};

} // namespace zawa
#line 4 "Src/DataStructure/SegmentTree/DualSegmentTree.hpp"

namespace zawa {

template <concepts::Monoid Monoid>
class DualSegmentTree : public CommutativeDualSegmentTree<Monoid> {
private:

    using Base = CommutativeDualSegmentTree<Monoid>;
    
public:

    using OM = Monoid;

    using O = typename OM::Element;

    using VM = Monoid;

    using V = typename VM::Element;

    DualSegmentTree() : Base() {}

    explicit DualSegmentTree(usize n) : Base{n} {}

    explicit DualSegmentTree(const std::vector<O>& dat) : Base{dat} {}

    template <class InputIterator>
    DualSegmentTree(InputIterator first, InputIterator last) : Base(first, last) {}
    
    void operation(usize l, usize r, const O& o) override {
        Base::push(l);
        if (l < r) Base::push(r - 1);
        Base::operation(l, r, o);
    } 

    void operation(usize i, const O& o) override {
        Base::push(i);
        Base::operation(i, o);
    }

    V operator[](usize i) override {
        Base::push(i);
        return Base::operator[](i);
    }
};

} // namespace zawa
#line 4 "Test/AOJ/DSL_2_D.test.cpp"

#line 6 "Test/AOJ/DSL_2_D.test.cpp"
#include <iostream>
#line 8 "Test/AOJ/DSL_2_D.test.cpp"

using namespace zawa;

struct M {
    using Element = int;
    static int identity() {
        return -1;
    }
    static int operation(int a, int b) {
        return (b == identity() ? a : b);
    }
};

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n, q; std::cin >> n >> q;
    DualSegmentTree<M> seg(std::vector<int>(n, (1LL << 31) - 1));
    while (q--) {
        int t; std::cin >> t;
        if (t == 0) {
            int l, r, x; std::cin >> l >> r >> x;
            seg.operation(l, r + 1, x);
        }
        else if (t == 1) {
            int i; std::cin >> i;
            std::cout << seg[i] << '\n';
        }
        else {
            assert(false);
        }
    }
}
Back to top page