静的列の区間クエリをオフライン処理する
(Src/Sequence/OfflineRangeProduct.hpp)

• View this file on GitHub
• Last update: 2025-08-21 03:06:56+09:00
• Include: #include "Src/Sequence/OfflineRangeProduct.hpp"

ライブラリの使い方

template <class M, class S, class Range>
requires concepts::Monoid<M> and concepts::Acted<M, S> and offline_range_product_internal::Range<Range>
std::vector<typename M::Element> OfflineRangeProduct(const std::vector<S>& as, const std::vector<Range>& qs)

Mはモノイドであり、 $S$ はM::Elementに作用する。

M::Element = Sの場合はそのままMのみをテンプレート引数に渡せば良い。(actedを呼び出す所がoperationに置き換わる)

雛形

struct M {
    using Element = ;
    static Element identity() {
    }
    static Element operation(Element L, Element R) {
    }
    static Element acted(Element E, S s) {
    }
};

Rangeは単にl, rというusizeにキャストできるメンバがあれば良い。半開区間で与えること。

struct query {
    usize l, r;
};

計算量

actedを $\Theta (N\log N)$ 回。operationを $\Theta (Q)$ 回。identityを $\Theta (N + Q)$ 回呼び出す。

参考

• 分割統治による静的列の区間積クエリ

Depends on

• Src/Algebra/Action/ActionConcept.hpp
• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AtCoder/abc223_h.test.cpp
• Test/LC/staticrmq/OfflineRangeProduct.test.cpp

Code

#pragma once

#include "../Template/TypeAlias.hpp"
#include "../Algebra/Monoid/MonoidConcept.hpp"
#include "../Algebra/Action/ActionConcept.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <numeric>
#include <vector>

namespace zawa {

namespace offline_range_product_internal {

template <class R>
concept Range = requires (R lr) {
    { lr.l } -> std::convertible_to<usize>;
    { lr.r } -> std::convertible_to<usize>;
};

template <class M, class S, class R>
concept condition = concepts::Monoid<M> and Range<R> and (std::same_as<typename M::Element, S> or concepts::Acted<M, S>);

} // namespace offline_range_product_internal

template <class M, class S, class Range>
requires offline_range_product_internal::condition<M, S, Range>
std::vector<typename M::Element> OfflineRangeProduct(const std::vector<S>& as, const std::vector<Range>& qs) {
    std::vector<typename M::Element> sum(as.size() + 1), res(qs.size(), M::identity());
    auto f = [&](usize m, const std::vector<usize>& idx) -> void {
        sum[m] = M::identity();
        usize L = m, R = m;
        for (usize i : idx) {
            L = std::min<usize>(L, qs[i].l);
            R = std::max<usize>(R, qs[i].r);
        }
        for (usize i = m ; i-- > L ; ) {
            if constexpr (std::same_as<typename M::Element, S>)
                sum[i] = M::operation(as[i], sum[i + 1]);
            else
                sum[i] = M::acted(sum[i + 1], as[i]);
        }
        for (usize i = m ; i < R ; i++) {
            if constexpr (std::same_as<typename M::Element, S>)
                sum[i + 1] = M::operation(sum[i], as[i]);
            else
                sum[i + 1] = M::acted(sum[i], as[i]);
        }
        for (usize i : idx)
            res[i] = M::operation(sum[qs[i].l], sum[qs[i].r]);
    };
    auto rec = [&](auto rec, usize L, usize R, std::vector<usize> idx) -> void {
        if (L >= R)
            return;
        if (L + 1 == R) {
            f(L, idx);
            return;
        }
        const usize mid = (L + R) / 2;
        std::vector<usize> toL, toR, cur;
        for (auto&& i : idx) {
            assert(qs[i].l <= qs[i].r and static_cast<usize>(qs[i].r) <= as.size());
            if (static_cast<usize>(qs[i].r) <= mid)
                toL.push_back(std::move(i));
            else if (mid <= static_cast<usize>(qs[i].l))
                toR.push_back(std::move(i));
            else
                cur.push_back(std::move(i));
        }
        if (cur.size())
            f(mid, cur);
        if (toL.size())
            rec(rec, L, mid, toL);
        if (toR.size())
            rec(rec, mid, R, toR);
    };
    std::vector<usize> idx(qs.size());
    std::iota(idx.begin(), idx.end(), 0);
    rec(rec, 0, as.size(), idx);
    return res;
}

} // namespace zawa

#line 2 "Src/Sequence/OfflineRangeProduct.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 2 "Src/Algebra/Action/ActionConcept.hpp"

#line 4 "Src/Algebra/Action/ActionConcept.hpp"

namespace zawa {

namespace concepts {

template <class G, class X>
concept Action = requires {
    typename G::Element;
    { G::action(std::declval<typename G::Element>(), std::declval<X>()) } -> std::same_as<X>;
};

// Is appropriate name X-set?
template <class G, class X>
concept Acted = requires {
    typename G::Element;
    { G::acted(std::declval<typename G::Element>(), std::declval<X>()) } -> std::same_as<typename G::Element>;
};

} // namespace concepts

} // namespace zawa
#line 6 "Src/Sequence/OfflineRangeProduct.hpp"

#include <algorithm>
#include <cassert>
#line 10 "Src/Sequence/OfflineRangeProduct.hpp"
#include <numeric>
#include <vector>

namespace zawa {

namespace offline_range_product_internal {

template <class R>
concept Range = requires (R lr) {
    { lr.l } -> std::convertible_to<usize>;
    { lr.r } -> std::convertible_to<usize>;
};

template <class M, class S, class R>
concept condition = concepts::Monoid<M> and Range<R> and (std::same_as<typename M::Element, S> or concepts::Acted<M, S>);

} // namespace offline_range_product_internal

template <class M, class S, class Range>
requires offline_range_product_internal::condition<M, S, Range>
std::vector<typename M::Element> OfflineRangeProduct(const std::vector<S>& as, const std::vector<Range>& qs) {
    std::vector<typename M::Element> sum(as.size() + 1), res(qs.size(), M::identity());
    auto f = [&](usize m, const std::vector<usize>& idx) -> void {
        sum[m] = M::identity();
        usize L = m, R = m;
        for (usize i : idx) {
            L = std::min<usize>(L, qs[i].l);
            R = std::max<usize>(R, qs[i].r);
        }
        for (usize i = m ; i-- > L ; ) {
            if constexpr (std::same_as<typename M::Element, S>)
                sum[i] = M::operation(as[i], sum[i + 1]);
            else
                sum[i] = M::acted(sum[i + 1], as[i]);
        }
        for (usize i = m ; i < R ; i++) {
            if constexpr (std::same_as<typename M::Element, S>)
                sum[i + 1] = M::operation(sum[i], as[i]);
            else
                sum[i + 1] = M::acted(sum[i], as[i]);
        }
        for (usize i : idx)
            res[i] = M::operation(sum[qs[i].l], sum[qs[i].r]);
    };
    auto rec = [&](auto rec, usize L, usize R, std::vector<usize> idx) -> void {
        if (L >= R)
            return;
        if (L + 1 == R) {
            f(L, idx);
            return;
        }
        const usize mid = (L + R) / 2;
        std::vector<usize> toL, toR, cur;
        for (auto&& i : idx) {
            assert(qs[i].l <= qs[i].r and static_cast<usize>(qs[i].r) <= as.size());
            if (static_cast<usize>(qs[i].r) <= mid)
                toL.push_back(std::move(i));
            else if (mid <= static_cast<usize>(qs[i].l))
                toR.push_back(std::move(i));
            else
                cur.push_back(std::move(i));
        }
        if (cur.size())
            f(mid, cur);
        if (toL.size())
            rec(rec, L, mid, toL);
        if (toR.size())
            rec(rec, mid, R, toR);
    };
    std::vector<usize> idx(qs.size());
    std::iota(idx.begin(), idx.end(), 0);
    rec(rec, 0, as.size(), idx);
    return res;
}

} // namespace zawa

Back to top page