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/LC/staticrmq/OfflineRangeProduct.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include "../../../Src/Sequence/OfflineRangeProduct.hpp"

#include <algorithm>
#include <vector>
#include <iostream>

using namespace zawa;
using namespace std;
struct M {
    using Element = int;
    static Element identity() {
        return 2000000000;
    }
    static Element operation(Element L, Element R) {
        return min(L, R);
    }
};
struct query {
    int l, r;
};
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    for (int i = 0 ; i < N ; i++)
        cin >> a[i];
    vector<query> q(Q);
    for (int i = 0 ; i < Q ; i++) {
        int l, r;
        cin >> l >> r;
        q[i] = {l, r};
    }
    for (int ans : OfflineRangeProduct<M>(a, q))
        cout << ans << '\n';
}
#line 1 "Test/LC/staticrmq/OfflineRangeProduct.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#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
#line 4 "Test/LC/staticrmq/OfflineRangeProduct.test.cpp"

#line 7 "Test/LC/staticrmq/OfflineRangeProduct.test.cpp"
#include <iostream>

using namespace zawa;
using namespace std;
struct M {
    using Element = int;
    static Element identity() {
        return 2000000000;
    }
    static Element operation(Element L, Element R) {
        return min(L, R);
    }
};
struct query {
    int l, r;
};
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    for (int i = 0 ; i < N ; i++)
        cin >> a[i];
    vector<query> q(Q);
    for (int i = 0 ; i < Q ; i++) {
        int l, r;
        cin >> l >> r;
        q[i] = {l, r};
    }
    for (int ans : OfflineRangeProduct<M>(a, q))
        cout << ans << '\n';
}
Back to top page