verify/aoj-2842-binary_indexed_tree_2d.test.cpp

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/2842

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2842"

#include <iostream>
#include <queue>
#include <tuple>

#include "../algorithm/DataStructure/SegmentTree/binary_indexed_tree_2d.hpp"

int main() {
    int y, x;
    int t;
    int q;
    std::cin >> y >> x >> t >> q;

    algorithm::binary_indexed_tree_2d::range_sum_binary_indexed_tree_2d<int> raw(y, x), baked(y, x);
    std::queue<std::tuple<int, int, int> > que;
    while(q--) {
        int time;
        int c;
        std::cin >> time >> c;

        while(!que.empty()) {
            auto [end, y, x] = que.front();
            if(time < end) break;
            que.pop();

            raw.add(y, x, -1);
            baked.add(y, x, 1);
        }

        if(c == 0) {
            int y, x;
            std::cin >> y >> x;
            y--, x--;

            raw.add(y, x, 1);
            que.emplace(time + t, y, x);
        } else if(c == 1) {
            int y, x;
            std::cin >> y >> x;
            y--, x--;

            if(baked.sum(y, x, y + 1, x + 1) >= 1) baked.add(y, x, -1);
        } else {
            int y, x, yy, xx;
            std::cin >> y >> x >> yy >> xx;
            y--, x--;

            auto &&a = baked.sum(y, x, yy, xx);
            auto &&b = raw.sum(y, x, yy, xx);
            std::cout << a << " " << b << "\n";
        }
    }
}

#line 1 "verify/aoj-2842-binary_indexed_tree_2d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2842"

#include <iostream>
#include <queue>
#include <tuple>

#line 1 "algorithm/DataStructure/SegmentTree/binary_indexed_tree_2d.hpp"



#include <algorithm>
#include <cassert>
#include <vector>

#line 1 "algorithm/Math/Algebra/algebra.hpp"



#line 6 "algorithm/Math/Algebra/algebra.hpp"
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>

namespace algorithm {

namespace algebra {

template <typename S>
class Set {
public:
    using value_type = S;

protected:
    value_type val;

public:
    constexpr Set() : val() {}
    constexpr Set(const value_type &val) : val(val) {}
    constexpr Set(value_type &&val) : val(std::move(val)) {}

    friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.val == rhs.val; }
    friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
    friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.val; }

    constexpr value_type value() const { return val; }
};

template <typename S, auto op>
class Semigroup : public Set<S> {
    static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);

    using base_type = Set<S>;

public:
    using value_type = typename base_type::value_type;

    constexpr Semigroup() : base_type() {}
    constexpr Semigroup(const value_type &val) : base_type(val) {}
    constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.val, rhs.val)); }

    static constexpr auto get_op() { return op; }
};

template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
    static_assert(std::is_invocable_r<S, decltype(e)>::value);

    using base_type = Semigroup<S, op>;

public:
    using value_type = typename base_type::value_type;

    constexpr Monoid() : base_type() {}
    constexpr Monoid(const value_type &val) : base_type(val) {}
    constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.val, rhs.val)); }

    static constexpr auto get_e() { return e; }
    static constexpr Monoid one() { return Monoid(e()); }  // return identity element.
};

template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
    static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);

    using base_type = Monoid<S, op, e>;

public:
    using value_type = typename base_type::value_type;

    constexpr Group() : base_type() {}
    constexpr Group(const value_type &val) : base_type(val) {}
    constexpr Group(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.val, rhs.val)); }

    static constexpr auto get_inverse() { return inverse; }
    static constexpr Group one() { return Group(e()); }                // return identity element.
    constexpr Group inv() const { return Group(inverse(this->val)); }  // return inverse element.
};

template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
    static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);

    using base_type = Monoid<F, compose, id>;

public:
    using value_type = typename base_type::value_type;
    using acted_value_type = X;

    constexpr OperatorMonoid() : base_type() {}
    constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
    constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.val, rhs.val)); }

    static constexpr auto get_mapping() { return mapping; }
    static constexpr OperatorMonoid one() { return OperatorMonoid(id()); }  // return identity mapping.
    constexpr acted_value_type act(const acted_value_type &x) const { return mapping(this->val, x); }
    template <class S>
    constexpr S act(const S &x) const {
        static_assert(std::is_base_of<Set<acted_value_type>, S>::value);
        return S(mapping(this->val, x.value()));
    }
};

namespace element {

template <typename S>
constexpr auto zero = []() -> S { return S(); };

template <typename S>
constexpr auto one = []() -> S { return 1; };

template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };

template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };

template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };

template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };

template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };

}  // namespace element

namespace uoperator {

template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };

template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };

}  // namespace uoperator

namespace boperator {

template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };

template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };

template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };

template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };

template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };

template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };

template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
    static_assert(std::is_invocable_r<F, decltype(id)>::value);
    return (lhs == id() ? rhs : lhs);
};

}  // namespace boperator

namespace monoid {

template <typename S>
using minimum = Monoid<S, boperator::min<S>, element::max<S>>;

template <typename S>
using minimum_safe = Monoid<S, boperator::min<S>, element::one_below_max<S>>;

template <typename S>
using maximum = Monoid<S, boperator::max<S>, element::lowest<S>>;

template <typename S>
using maximum_safe = Monoid<S, boperator::max<S>, element::one_above_lowest<S>>;

template <typename S>
using addition = Monoid<S, boperator::plus<S>, element::zero<S>>;

template <typename S>
using multiplication = Monoid<S, boperator::mul<S>, element::one<S>>;

template <typename S>
using bit_xor = Monoid<S, boperator::bit_xor<S>, element::zero<S>>;

}  // namespace monoid

namespace group {

template <typename S>
using addition = Group<S, boperator::plus<S>, element::zero<S>, uoperator::negate<S>>;

template <typename S>
using bit_xor = Group<S, boperator::bit_xor<S>, element::zero<S>, uoperator::identity<S>>;

}  // namespace group

namespace operator_monoid {

template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
    F, boperator::assign_if_not_id<F, element::max<F>>, element::max<F>,
    X, boperator::assign_if_not_id<F, element::max<F>, X>>;

template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
    F, boperator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
    X, boperator::assign_if_not_id<F, element::lowest<F>, X>>;

template <typename F, typename X = F>
using addition = OperatorMonoid<F, boperator::plus<F>, element::zero<F>, X, boperator::plus<F, X>>;

}  // namespace operator_monoid

}  // namespace algebra

}  // namespace algorithm


#line 9 "algorithm/DataStructure/SegmentTree/binary_indexed_tree_2d.hpp"

namespace algorithm {

namespace binary_indexed_tree_2d {

template <class AbelianGroup>
class BIT2D {
public:
    using group_type = AbelianGroup;
    using value_type = group_type::value_type;

private:
    int m_h, m_w;
    std::vector<std::vector<group_type>> m_tree;

    static constexpr int lsb(int bit) { return bit & -bit; }
    group_type sum_internal(int y, int x) const {
        group_type &&res = group_type::one();
        for(int i = y; i >= 1; i -= lsb(i)) {
            for(int j = x; j >= 1; j -= lsb(j)) res = res * m_tree[i - 1][j - 1];
        }
        return res;
    }
    void build() {
        for(int i = 1; i <= m_h; ++i) {
            int ni = i + lsb(i);
            for(int j = 1; j <= m_w; ++j) {
                int nj = j + lsb(j);
                if(ni <= m_h) m_tree[ni - 1][j - 1] = m_tree[ni - 1][j - 1] * m_tree[i - 1][j - 1];
                if(nj <= m_w) {
                    m_tree[i - 1][nj - 1] = m_tree[i - 1][nj - 1] * m_tree[i - 1][j - 1];
                    if(ni <= m_h) m_tree[ni - 1][nj - 1] = m_tree[ni - 1][nj - 1] * m_tree[i - 1][j - 1].inv();
                }
            }
        }
    }

public:
    // constructor. O(H*W).
    BIT2D() : BIT2D(0, 0) {}
    explicit BIT2D(int h, int w) : m_h(h), m_w(w), m_tree(h, std::vector<group_type>(w, group_type::one())) {
        assert(h >= 0 and w >= 0);
    }
    explicit BIT2D(int h, int w, const value_type &a) : BIT2D(h, w, group_type(a)) {}
    explicit BIT2D(int h, int w, const group_type &a) : m_h(h), m_w(w), m_tree(h, std::vector<group_type>(w, a)) {
        assert(h >= 0 and w >= 0);
        build();
    }

    int height() const { return m_h; }
    int width() const { return m_w; }
    // (y,x)にある要素をaとの積の結果に置き換える．O((log H) log W).
    void add(int y, int x, const value_type &a) { add(y, x, group_type(a)); }
    void add(int y, int x, const group_type &a) {
        assert(0 <= y and y < height());
        assert(0 <= x and x < width());
        for(int i = y + 1; i <= m_h; i += lsb(i)) {
            for(int j = x + 1; j <= m_w; j += lsb(j)) m_tree[i - 1][j - 1] = m_tree[i - 1][j - 1] * a;
        }
    }
    // [0,y)かつ[0,x)の範囲にある要素の総積を求める．O((log H) log W).
    value_type sum(int y, int x) const {
        assert(0 <= y and y <= height());
        assert(0 <= x and x <= width());
        return sum_internal(y, x).value();
    }
    // [y,yy)かつ[x,xx)の範囲にある要素の総積を求める．O((log H) log W).
    value_type sum(int y, int x, int yy, int xx) const {
        assert(0 <= y and y <= yy and yy <= height());
        assert(0 <= x and x <= xx and xx <= width());
        return (sum_internal(yy, xx) * sum_internal(yy, x).inv() * sum_internal(y, xx).inv() * sum_internal(y, x)).value();
    }
    // 全要素の総積を求める．O((log H) log W).
    value_type sum_all() const { return sum_internal(m_h, m_w).value(); }
    void reset() {
        for(auto &v : m_tree) std::fill(v.begin(), v.end(), group_type::one());
    }
};

template <typename S>
using range_sum_binary_indexed_tree_2d = BIT2D<algebra::group::addition<S>>;

}  // namespace binary_indexed_tree_2d

}  // namespace algorithm


#line 8 "verify/aoj-2842-binary_indexed_tree_2d.test.cpp"

int main() {
    int y, x;
    int t;
    int q;
    std::cin >> y >> x >> t >> q;

    algorithm::binary_indexed_tree_2d::range_sum_binary_indexed_tree_2d<int> raw(y, x), baked(y, x);
    std::queue<std::tuple<int, int, int> > que;
    while(q--) {
        int time;
        int c;
        std::cin >> time >> c;

        while(!que.empty()) {
            auto [end, y, x] = que.front();
            if(time < end) break;
            que.pop();

            raw.add(y, x, -1);
            baked.add(y, x, 1);
        }

        if(c == 0) {
            int y, x;
            std::cin >> y >> x;
            y--, x--;

            raw.add(y, x, 1);
            que.emplace(time + t, y, x);
        } else if(c == 1) {
            int y, x;
            std::cin >> y >> x;
            y--, x--;

            if(baked.sum(y, x, y + 1, x + 1) >= 1) baked.add(y, x, -1);
        } else {
            int y, x, yy, xx;
            std::cin >> y >> x >> yy >> xx;
            y--, x--;

            auto &&a = baked.sum(y, x, yy, xx);
            auto &&b = raw.sum(y, x, yy, xx);
            std::cout << a << " " << b << "\n";
        }
    }
}