Test/LC/static_range_sum.test.cpp

View this file on GitHub
Last update: 2023-07-22 13:55:49+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

Code

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

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp" 

#include <cstdio>
#include <vector>

using namespace zawa;

i32 main() {
    u32 N, Q;
    std::scanf("%u%u", &N, &Q); 
    std::vector<i64> A(N);
    for (auto& a : A) std::scanf("%ld", &a);

    Ruisekiwa<i64> S(A);
    for (u32 _ = 0 ; _ < Q ; _++) {
        u32 l, r;
        std::scanf("%u%u", &l, &r);
        std::printf("%ld\n", S.product(l, r));
    }
}

#line 1 "Test/LC/static_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#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/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp"

#line 2 "Src/Algebra/Group/AdditiveGroup.hpp"

namespace zawa {

template <class T>
class AdditiveGroup {
public:
    using Element = T;
    static constexpr T identity() noexcept {
        return T{};
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        return l + r;
    }
    static constexpr T inverse(const T& v) noexcept {
        return -v;
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

#line 4 "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <type_traits>
#include <functional>

namespace zawa {

template <class Group>
class PrefixSum1D {
private:
    using T = typename Group::Element;
    std::vector<T> dat_;

    constexpr bool rangeCheck(u32 l, u32 r) const {
        return (l <= r and r < dat_.size());
    }

public:
    PrefixSum1D() = default; 
    PrefixSum1D(const std::vector<T>& A) : dat_(A.size() + 1, Group::identity()) {
        dat_.shrink_to_fit();
        for (u32 i = 0 ; i < A.size() ; i++) {
            dat_[i + 1] = Group::operation(dat_[i], A[i]);
        }
    }

    inline T operator[](u32 i) const {
        assert(i < dat_.size());
        return dat_[i];
    }

    inline usize size() const {
        return dat_.size();
    }

    T product(u32 l, u32 r) const {
        assert(rangeCheck(l, r));
        return Group::operation(Group::inverse(dat_[l]), dat_[r]);
    }

    u32 lowerBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::lower_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    u32 upperBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::upper_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    template <class F>
    u32 maxRight(u32 l, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(l < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(v, Group::inverse(dat_[l])));
        };
        return std::partition_point(dat_.begin() + l, dat_.end(), f_) - dat_.begin();
    }

    template <class F>
    u32 minLeft(u32 r, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(r < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(Group::inverse(v), dat_[r]));
        };
        return dat_.rend() - std::partition_point(dat_.rbegin() + (dat_.size() - r - 1), dat_.rend(), f_) - 1;
    }

    const auto begin() const {
        return dat_.begin();
    }

    const auto end() const {
        return dat_.end();
    }
};

} // namespace zawa
#line 5 "Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp"

namespace zawa {

    template <class T>
    using StaticRangeSumSolver = PrefixSum1D<AdditiveGroup<T>>;

    template <class T>
    using Ruisekiwa = PrefixSum1D<AdditiveGroup<T>>;

};
#line 5 "Test/LC/static_range_sum.test.cpp"

#include <cstdio>
#line 8 "Test/LC/static_range_sum.test.cpp"

using namespace zawa;

i32 main() {
    u32 N, Q;
    std::scanf("%u%u", &N, &Q); 
    std::vector<i64> A(N);
    for (auto& a : A) std::scanf("%ld", &a);

    Ruisekiwa<i64> S(A);
    for (u32 _ = 0 ; _ < Q ; _++) {
        u32 l, r;
        std::scanf("%u%u", &l, &r);
        std::printf("%ld\n", S.product(l, r));
    }
}