Test/AOJ/2426.test.cpp

• View this file on GitHub
• Last update: 2025-12-23 18:04:55+09:00
• Problem: http://onlinejudge.u-aizu.ac.jp/problems/2426

Depends on

• 加法群 (Src/Algebra/Group/AdditiveGroup.hpp)
• Src/Algebra/Group/GroupConcept.hpp
• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp
• Src/DataStructure/PrefixSum/PrefixSum2D.hpp
• 座標圧縮 (Src/Sequence/CompressedSequence.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

#define PROBLEM "http://onlinejudge.u-aizu.ac.jp/problems/2426"

#include "../../Src/Algebra/Group/AdditiveGroup.hpp"
#include "../../Src/DataStructure/PrefixSum/PrefixSum2D.hpp"
#include "../../Src/Sequence/CompressedSequence.hpp"
using namespace zawa;

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    vector<int> X(N), Y(N);
    for (int i = 0 ; i < N ; i++)
        cin >> X[i] >> Y[i];
    CompressedSequence CX{X}, CY{Y};
    Ruisekiwa2D<AdditiveGroup<int>> a{CX.size(), CY.size()};
    for (int i = 0 ; i < N ; i++) 
        a.operation(CX.map(i), CY.map(i), 1);
    auto sum = a.inplaceBuild();
    while (M--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << sum.product(CX[x1], CY[y1], CX[x2 + 1], CY[y2 + 1]) << '\n';
    }
}

#line 1 "Test/AOJ/2426.test.cpp"
#define PROBLEM "http://onlinejudge.u-aizu.ac.jp/problems/2426"

#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/PrefixSum/PrefixSum2D.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/Group/GroupConcept.hpp"

#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 4 "Src/Algebra/Group/GroupConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Inversible = requires {
    typename T::Element;
    { T::inverse(std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

template <class T>
concept Group = Monoid<T> and Inversible<T>;

} // namespace Concept

} // namespace zawa
#line 5 "Src/DataStructure/PrefixSum/PrefixSum2D.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

namespace internal {

template <concepts::Group G>
class StaticRectSumSolver {
public:
    
    using T = typename G::Element;

    using const_iterator = typename std::vector<std::vector<T>>::const_iterator;

    explicit StaticRectSumSolver(const std::vector<std::vector<T>>& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_sum(m_H + 1, std::vector<T>(m_W + 1, G::identity())) {
        for (usize i = 0 ; i < m_H ; i++)
            for (usize j = 0 ; j < m_W ; j++)
                m_sum[i + 1][j + 1] = G::operation(
                        G::operation(m_sum[i + 1][j], m_sum[i][j + 1]), 
                        G::operation(G::inverse(m_sum[i][j]), a[i][j])
                        );
    }

    explicit StaticRectSumSolver(std::vector<std::vector<T>>&& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_sum{std::move(a)} {
        for (usize i = 0 ; i < m_H ; i++)
            m_sum[i].push_back(G::identity());
        m_sum.push_back(std::vector<T>(m_W + 1, G::identity()));
        for (usize i = 0 ; i <= m_H ; i++)
            for (usize j = m_W ; j-- ; )
                m_sum[i][j] = G::operation(m_sum[i][j], m_sum[i][j + 1]);
        for (usize i = m_H ; i-- ; )
            for (usize j = 0 ; j <= m_W ; j++)
                m_sum[i][j] = G::operation(m_sum[i][j], m_sum[i + 1][j]);
    }

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    // [l, r) x [d, u)
    T product(usize l, usize d, usize r, usize u) const {
        assert((l <= r and r <= height()) and "invalid i range: StaticRectSumSolver::product");
        assert((d <= u and u <= width()) and "invalid j range: StaticRectSumSolver::product");
        return G::operation(
                G::operation(m_sum[r][u], m_sum[l][d]),
                G::inverse(G::operation(m_sum[r][d], m_sum[l][u]))
                );
    }

    const std::vector<T>& operator[](usize i) const {
        assert(i <= height() and "invalid access m_sum[i]: StaticRectSumSolver::operator[]");
        return m_sum[i];
    }

    const_iterator begin() const {
        return m_sum.begin();
    }
    
    const_iterator end() const {
        return m_sum.end();
    }

private:

    usize m_H, m_W;

    std::vector<std::vector<T>> m_sum;
};

} // namespace internal

template <concepts::Group G>
class Ruisekiwa2D {
public:
    
    using T = typename G::Element;

    Ruisekiwa2D(usize H, usize W) : m_H{H}, m_W{W}, m_a(H, std::vector<T>(W, G::identity())) {}

    explicit Ruisekiwa2D(std::vector<std::vector<T>>&& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_a{std::move(a)} {}

    explicit Ruisekiwa2D(const std::vector<std::vector<T>>& a) : m_H{a.size()}, m_W{a.empty() ? 0u : a[0].size()}, m_a{a} {}

    inline usize height() const {
        return m_H;
    }

    inline usize width() const {
        return m_W;
    }

    void operation(usize i, usize j, T v) {
        assert((i < height() and j < width()) and "invalid range: Ruisekiwa2D::operation");
        assert(m_moved == false and "already destructed: Ruisekiwa2D::operation");
        m_a[i][j] = G::operation(m_a[i][j], v);
    }

    const std::vector<T>& operator[](const usize i) const {
        assert(i < height() and "invalid range: Ruisekiwa2D::operator[]");
        assert(m_moved == false and "already destructed: Ruisekiwa2D::operator[]");
        return m_a[i];
    }

    internal::StaticRectSumSolver<G> build() const {
        assert(m_moved == false and "already destructed: Ruisekiwa2D::build");
        return internal::StaticRectSumSolver<G>{m_a};
    }

    internal::StaticRectSumSolver<G> inplaceBuild() {
        assert(m_moved == false and "already destructed: Ruisekiwa2D::build");
        m_moved = true;
        return internal::StaticRectSumSolver<G>{std::move(m_a)};
    }

private:

    usize m_H = 0, m_W = 0;

    std::vector<std::vector<T>> m_a;

    bool m_moved = false;
};

} // namespace zawa
#line 2 "Src/Sequence/CompressedSequence.hpp"

#line 4 "Src/Sequence/CompressedSequence.hpp"

#line 6 "Src/Sequence/CompressedSequence.hpp"
#include <algorithm>
#line 8 "Src/Sequence/CompressedSequence.hpp"
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
#line 6 "Test/AOJ/2426.test.cpp"
using namespace zawa;

#include <iostream>
#line 10 "Test/AOJ/2426.test.cpp"
using namespace std;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    vector<int> X(N), Y(N);
    for (int i = 0 ; i < N ; i++)
        cin >> X[i] >> Y[i];
    CompressedSequence CX{X}, CY{Y};
    Ruisekiwa2D<AdditiveGroup<int>> a{CX.size(), CY.size()};
    for (int i = 0 ; i < N ; i++) 
        a.operation(CX.map(i), CY.map(i), 1);
    auto sum = a.inplaceBuild();
    while (M--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << sum.product(CX[x1], CY[y1], CX[x2 + 1], CY[y2 + 1]) << '\n';
    }
}

Back to top page