区間Prefix総積モノイド
(Src/Algebra/Monoid/PrefixProductMonoid.hpp)

• View this file on GitHub
• Last update: 2024-02-06 13:31:29+09:00
• Include: #include "Src/Algebra/Monoid/PrefixProductMonoid.hpp"

概要

セグ木とかのモノイドで抽象化できるデータ構造に乗るやつ。

列 $A$ 上の区間 $[l, r)$ に対して

$g_{l, r}(A) = g(A_{l}, f(A_{l}, A_{l + 1}), f(A_{l}, A_{l + 1}, A_{l + 2}), \dots, f(A_{l}, A_{l + 1}, \dots, A_{r}))$ を管理する。

例えば $\max(A_{1}, A_{1} + A_{2}, \dots, A_{1} + A_{2} + \dots, A_{N})$ とか…

え？これ遅延伝搬いらないんすね。うお〜〜〜〜。

使い方

template <class Value>
class PrefixProductMonoidData(const Value& product, const Value& prefix)

template <class O, class F>
class PrefixProductMonoid

PrefixProductMonoidDataはproduct, prefixのゲッタだけ提供する。

• productは $f(A_{l}, A_{l + 1}, \dots, A_{r})$
• prefix は $g_{l, r}(A)$

PrefixProductMonoidはElement, identity(), operation()を提供するクラス。

テンプレート引数について、O は $f$ 、 Fは $g$ のモノイドを与える必要がある。

参考

• ABC292-H Editional

Verified with

• Test/AtCoder/abc292_h.test.cpp

Code

#pragma once

#include <type_traits>

namespace zawa {

template <class Value>
class PrefixProductMonoidData {
    Value product_{}, prefix_{};
public:
    PrefixProductMonoidData() = default;
    PrefixProductMonoidData(const Value& product, const Value& prefix)
        : product_{product}, prefix_{prefix} {}

    inline const Value& product() const noexcept {
        return product_;
    }
    inline const Value& prefix() const noexcept {
        return prefix_;
    }
};

template <class O, class F>
class PrefixProductMonoid {
    static_assert(std::is_same_v<typename O::Element, typename F::Element>);
public:
    using Element = PrefixProductMonoidData<typename O::Element>;
    static Element identity() noexcept {
        return PrefixProductMonoidData{O::identity(), F::identity()};
    }
    static Element operation(const Element& l, const Element& r) noexcept {
        return PrefixProductMonoidData{
            O::operation(l.product(), r.product()),
            F::operation(l.prefix(), O::operation(l.product(), r.prefix()))
        };
    }
};

} // namespace zawa

#line 2 "Src/Algebra/Monoid/PrefixProductMonoid.hpp"

#include <type_traits>

namespace zawa {

template <class Value>
class PrefixProductMonoidData {
    Value product_{}, prefix_{};
public:
    PrefixProductMonoidData() = default;
    PrefixProductMonoidData(const Value& product, const Value& prefix)
        : product_{product}, prefix_{prefix} {}

    inline const Value& product() const noexcept {
        return product_;
    }
    inline const Value& prefix() const noexcept {
        return prefix_;
    }
};

template <class O, class F>
class PrefixProductMonoid {
    static_assert(std::is_same_v<typename O::Element, typename F::Element>);
public:
    using Element = PrefixProductMonoidData<typename O::Element>;
    static Element identity() noexcept {
        return PrefixProductMonoidData{O::identity(), F::identity()};
    }
    static Element operation(const Element& l, const Element& r) noexcept {
        return PrefixProductMonoidData{
            O::operation(l.product(), r.product()),
            F::operation(l.prefix(), O::operation(l.product(), r.prefix()))
        };
    }
};

} // namespace zawa

Back to top page