cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/datastructure/fenwick_tree/rectangle_add_rectangle_sum/dummy.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <iostream>
#include <random>

#include <atcoder/modint>
using mint = atcoder::modint998244353;

#include "library/datastructure/fenwick_tree/rectangle_add_rectangle_sum.hpp"
using suisen::RectangleAddRectangleSum;

template <typename T, int H, int W>
struct RectangleAddRectangleSumNaive {
    using value_type = T;
    RectangleAddRectangleSumNaive() {
        for (auto& row : _dat) row.fill(T{ 0 });
    }

    void add(int l, int r, int d, int u, const value_type& val) {
        for (int x = l; x < r; ++x) for (int y = d; y < u; ++y) _dat[x][y] += val;
    }

    value_type sum(int l, int r, int d, int u) const {
        value_type res{ 0 };
        for (int x = l; x < r; ++x) for (int y = d; y < u; ++y) res += _dat[x][y];
        return res;
    }
private:
    std::array<std::array<value_type, H>, W> _dat;
};


template <int H, int W, int Q>
void random_test(uint32_t seed = ~uint32_t(0)) {
    std::mt19937 rng{ seed != ~uint32_t(0) ? seed : std::random_device{}() };

    RectangleAddRectangleSumNaive<mint, H, W> sol1;
    RectangleAddRectangleSum<mint> sol2(H);

    using query_t = std::tuple<int, int, int, int, int>;

    std::vector<query_t> queries(Q);
    std::uniform_int_distribution<int> dist_x(0, H - 1), dist_y(0, W - 1), dist_val(0, mint::mod() - 1);

    for (int i = 0; i < Q; ++i) {
        int l = dist_x(rng), r = dist_x(rng);
        if (l > r) std::swap(l, r);
        int d = dist_y(rng), u = dist_y(rng);
        if (d > u) std::swap(d, u);
        if (rng() & 1) {
            int val = dist_val(rng);
            queries[i] = { l, r, d, u, val };
            sol2.register_add_query_rectangle(l, r, d, u);
        } else {
            queries[i] = { l, r, d, u, -1 };
        }
    }
    sol2.build();

    for (const auto& [l, r, d, u, v] : queries) {
        if (v >= 0) {
            sol1.add(l, r, d, u, v), sol2.add(l, r, d, u, v);
        } else {
            assert(sol1.sum(l, r, d, u) == sol2.sum(l, r, d, u));
        }
    }
}

int main() {
    random_test<1000, 1000, 2000>();
    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/src/datastructure/fenwick_tree/rectangle_add_rectangle_sum/dummy.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

#include <iostream>
#include <random>

#include <atcoder/modint>
using mint = atcoder::modint998244353;

#line 1 "library/datastructure/fenwick_tree/rectangle_add_rectangle_sum.hpp"



#line 1 "library/util/tuple_ops.hpp"



#include <tuple>

namespace suisen {
    namespace internal::tuple_ops {
        template <std::size_t N, typename F, typename ...Args>
        std::tuple<Args...>& update(std::tuple<Args...> &lhs, F &&fun) {
            if constexpr (N == std::tuple_size_v<std::tuple<Args...>>) return lhs;
            else return fun(std::get<N>(lhs)), update<N + 1>(lhs, std::forward<F>(fun));
        }
        template <std::size_t N, typename F, typename ...Args>
        std::tuple<Args...>& merge(std::tuple<Args...> &lhs, const std::tuple<Args...>& rhs, F &&fun) {
            if constexpr (N == std::tuple_size_v<std::tuple<Args...>>) return lhs;
            else return fun(std::get<N>(lhs), std::get<N>(rhs)), merge<N + 1>(lhs, rhs, std::forward<F>(fun));
        }
    }
    template <typename ...Args>
    std::tuple<Args...>& operator+=(std::tuple<Args...>& t1, const std::tuple<Args...>& t2) {
        return internal::tuple_ops::merge<0>(t1, t2, [](auto &x, const auto &y) { x += y; });
    }
    template <typename ...Args>
    std::tuple<Args...>& operator-=(std::tuple<Args...>& t1, const std::tuple<Args...>& t2) {
        return internal::tuple_ops::merge<0>(t1, t2, [](auto &x, const auto &y) { x -= y; });
    }
    template <typename ...Args>
    std::tuple<Args...> operator+(std::tuple<Args...> t1, const std::tuple<Args...>& t2) { return std::move(t1 += t2); }
    template <typename ...Args>
    std::tuple<Args...> operator-(std::tuple<Args...> t1, const std::tuple<Args...>& t2) { return std::move(t1 -= t2); }
    
    template <typename V, typename ...Args>
    std::tuple<Args...>& operator*=(std::tuple<Args...>& t1, const V &v) { return internal::tuple_ops::update<0>(t1, [&v](auto &x) { x *= v; }); }
    template <typename V, typename ...Args>
    std::tuple<Args...>& operator/=(std::tuple<Args...>& t1, const V &v) { return internal::tuple_ops::update<0>(t1, [&v](auto &x) { x /= v; }); }

    template <typename V, typename ...Args>
    std::tuple<Args...> operator*(const V &v, std::tuple<Args...> t1) { return std::move(t1 *= v); }
    template <typename V, typename ...Args>
    std::tuple<Args...> operator*(std::tuple<Args...> t1, const V &v) { return std::move(t1 *= v); }
    template <typename V, typename ...Args>
    std::tuple<Args...> operator/(std::tuple<Args...> t1, const V &v) { return std::move(t1 /= v); }
} // namespace suisen


#line 1 "library/datastructure/fenwick_tree/fenwick_tree_2d_sparse.hpp"



#include <algorithm>
#include <cassert>
#include <limits>
#line 8 "library/datastructure/fenwick_tree/fenwick_tree_2d_sparse.hpp"

#line 1 "library/datastructure/fenwick_tree/fenwick_tree.hpp"



#include <vector>
#include <map>
#include <unordered_map>

namespace suisen {
    namespace internal {
        template <typename T, typename index_t = int, typename Container = std::vector<T>>
        class FenwickTreeBase {
        public:
            FenwickTreeBase() = default;
            explicit FenwickTreeBase(index_t n) : n(n) {}

            int size() const {
                return n;
            }
            void add(index_t i, T v) {
                for (++i; i <= n; i += (i & -i)) data[i - 1] += v;
            }
            T sum(index_t l, index_t r) const {
                return sum(r) - sum(l);
            }
            auto operator[](int i) {
                struct {
                    int i;
                    FenwickTreeBase& ft;
                    operator T() const { return ft.sum(i, i + 1); }
                    auto& operator++() { return *this += 1; }
                    auto& operator--() { return *this -= 1; }
                    auto& operator+=(T val) { ft.add(i, val); return *this; }
                    auto& operator-=(T val) { ft.add(i, -val); return *this; }
                    auto& operator*=(T val) { T cur = ft.sum(i, i + 1); ft.add(i, cur * val - cur); return *this; }
                    auto& operator/=(T val) { T cur = ft.sum(i, i + 1); ft.add(i, cur / val - cur); return *this; }
                    auto& operator%=(T val) { T cur = ft.sum(i, i + 1); ft.add(i, cur % val - cur); return *this; }
                    auto& operator =(T val) { T cur = ft.sum(i, i + 1); ft.add(i, val - cur); return *this; }
                } obj{ i, *this };
                return obj;
            }
            T operator()(int l, int r) const { return sum(l, r); }

            Container& get_internal_container() { return data; }
        protected:
            index_t n;
            Container data;
            template <typename ...Args>
            FenwickTreeBase(index_t n, Args &&...args) : n(n), data(std::forward<Args>(args)...) {}
        private:
            T sum(int r) const {
                T s{};
                for (; r; r -= r & -r) s += data[r - 1];
                return s;
            }
        };

        template <typename Key, typename Value, bool unordered>
        using cond_map_t = std::conditional_t<unordered, std::unordered_map<Key, Value>, std::map<Key, Value>>;

    } // namespace internal

    template <typename T>
    struct FenwickTree : public internal::FenwickTreeBase<T> {
        FenwickTree() : FenwickTree(0) {}
        explicit FenwickTree(int n) : internal::FenwickTreeBase<T>::FenwickTreeBase(n, n, T{}) {}
        explicit FenwickTree(std::vector<T>&& a) : internal::FenwickTreeBase<T>::FenwickTreeBase(a.size(), std::move(a)) {
            for (int i = 1; i <= this->n; ++i) {
                int p = i + (i & -i);
                if (p <= this->n) this->data[p - 1] += this->data[i - 1];
            }
        }
        explicit FenwickTree(const std::vector<T>& a) : FenwickTree(std::vector<T>(a)) {}
    };

    template <typename T, typename index_t, bool use_unordered_map = false>
    using MapFenwickTree = internal::FenwickTreeBase<T, index_t, internal::cond_map_t<index_t, T, use_unordered_map>>;

} // namespace suisen


#line 10 "library/datastructure/fenwick_tree/fenwick_tree_2d_sparse.hpp"

namespace suisen {

    template <typename T>
    class FenwickTree2DSparse {
    public:
        FenwickTree2DSparse() = default;
        explicit FenwickTree2DSparse(int x_num) : n(x_num + 1), data(n), points(), pos_x(), pos_y(n) {}

        void add_point(int x, int y) {
            built = false;
            pos_x.push_back(x);
            points.emplace_back(x, y);
        }

        void build() {
            static constexpr int inf = std::numeric_limits<int>::max();
            built = true;
            pos_x.push_back(inf);
            std::sort(pos_x.begin(), pos_x.end());
            pos_x.erase(std::unique(pos_x.begin(), pos_x.end()), pos_x.end());
            assert(int(pos_x.size()) <= n);
            for (const auto& [x, y] : points) for (int k = comp_x(x) + 1; k <= n; k += k & -k) {
                pos_y[k - 1].push_back(y);
            }
            for (int k = 0; k < n; ++k) {
                pos_y[k].push_back(inf);
                std::sort(pos_y[k].begin(), pos_y[k].end());
                pos_y[k].erase(std::unique(pos_y[k].begin(), pos_y[k].end()), pos_y[k].end());
                data[k] = FenwickTree<T>(pos_y[k].size());
            }
        }

        // void build_and_init(const std::vector<std::tuple<int, int, T>> &points) {
        //     build();
        //     for (const auto &[x, y, w] : points) {
        //         int kx = comp_x(x), ky = comp_y(kx, y);
        //         data[kx].get_internal_container()[ky] += w;
        //     }
        //     for (int kx = n; kx; --kx) {
        //         auto &data_kx = data[kx - 1].get_internal_container();
        //         const int m = data[kx - 1].size();
        //         for (int ky = m; ky; --ky) {
        //             const int pky = ky + (ky & -ky);
        //             if (pky > m) continue;
        //             data_kx[pky - 1] += data[ky - 1];
        //         }
        //         const int pkx = kx + (kx & -kx);
        //         if (pkx > n) continue;
        //         auto &data_pkx = data[pkx - 1].get_internal_container();
        //         for (int ky = m; ky; --ky) {
        //             int y = pos_y[kx - 1][ky - 1];
        //             data_pkx[comp_y(pkx - 1, y)] += data_kx[ky - 1];
        //         }
        //     }
        // }

        T sum(int l, int r, int d, int u) const {
            return (*this)(l, r, d, u);
        }
        T operator()(int l, int r, int d, int u) const {
            assert(built);
            return sum(r, d, u) - sum(l, d, u);
        }

        T get(int x, int y) const {
            return (*this)(x, x + 1, y, y + 1);
        }
        void add(int x, int y, const T& val) {
            for (int k = comp_x(x) + 1; k <= n; k += k & -k) data[k - 1].add(comp_y(k - 1, y), val);
        }
        template <typename F>
        void apply(int x, int y, F &&f) {
            T old_val = get(x, y);
            add(x, y, f(old_val) - old_val);
        }
        void set(int x, int y, const T &val) {
            apply(x, y, [&](const T&) { return val; });
        }

    private:
        int n, m;
        std::vector<FenwickTree<T>> data;
        std::vector<std::pair<int, int>> points;
        std::vector<int> pos_x;
        std::vector<std::vector<int>> pos_y;
        bool built = true;

        int comp_x(int x) const {
            return std::lower_bound(pos_x.begin(), pos_x.end(), x) - pos_x.begin();
        }
        int comp_y(int k, int y) const {
            return std::lower_bound(pos_y[k].begin(), pos_y[k].end(), y) - pos_y[k].begin();
        }

        T sum(int r, int d, int u) const {
            T res{};
            for (r = comp_x(r); r; r -= r & -r) res += data[r - 1].sum(comp_y(r - 1, d), comp_y(r - 1, u));
            return res;
        }
    };
} // namespace suisen



#line 6 "library/datastructure/fenwick_tree/rectangle_add_rectangle_sum.hpp"

namespace suisen {
    template <typename T>
    struct RectangleAddRectangleSum {
        using value_type = T;
        using data_type = std::tuple<value_type, value_type, value_type, value_type>;

        RectangleAddRectangleSum() = default;
        explicit RectangleAddRectangleSum(int xnum) : _seg(xnum) {}

        void register_add_query_rectangle(int l, int r, int d, int u) {
            _seg.add_point(l, d), _seg.add_point(r, d);
            _seg.add_point(l, u), _seg.add_point(r, u);
        }
        void build() {
            _seg.build();
        }

        void add(int l, int r, int d, int u, const value_type& val) {
            add(l, d, val), add(r, d, -val);
            add(l, u, -val), add(r, u, val);
        }

        value_type sum(int l, int r, int d, int u) const {
            return sum(r, u) - sum(r, d) - sum(l, u) + sum(l, d);
        }

    private:
        static constexpr data_type op_data(data_type x, data_type y) { return x + y; }
        static constexpr data_type e_data() { return data_type{}; }

        FenwickTree2DSparse<data_type> _seg;

        void add(int l, int d, const value_type& v) {
            // v(x - l)(y - d) = v xy - vd x - vl y + vld
            _seg.add(l, d, data_type{ v, -v * d, -v * l, v * l * d });
        }

        value_type sum(int r, int u) const {
            static constexpr int inf = std::numeric_limits<int>::max();
            auto [a, b, c, d] = _seg.sum(-inf, r, -inf, u);
            return a * r * u + b * r + c * u + d;
        }
    };
} // namespace suisen


#line 10 "test/src/datastructure/fenwick_tree/rectangle_add_rectangle_sum/dummy.test.cpp"
using suisen::RectangleAddRectangleSum;

template <typename T, int H, int W>
struct RectangleAddRectangleSumNaive {
    using value_type = T;
    RectangleAddRectangleSumNaive() {
        for (auto& row : _dat) row.fill(T{ 0 });
    }

    void add(int l, int r, int d, int u, const value_type& val) {
        for (int x = l; x < r; ++x) for (int y = d; y < u; ++y) _dat[x][y] += val;
    }

    value_type sum(int l, int r, int d, int u) const {
        value_type res{ 0 };
        for (int x = l; x < r; ++x) for (int y = d; y < u; ++y) res += _dat[x][y];
        return res;
    }
private:
    std::array<std::array<value_type, H>, W> _dat;
};


template <int H, int W, int Q>
void random_test(uint32_t seed = ~uint32_t(0)) {
    std::mt19937 rng{ seed != ~uint32_t(0) ? seed : std::random_device{}() };

    RectangleAddRectangleSumNaive<mint, H, W> sol1;
    RectangleAddRectangleSum<mint> sol2(H);

    using query_t = std::tuple<int, int, int, int, int>;

    std::vector<query_t> queries(Q);
    std::uniform_int_distribution<int> dist_x(0, H - 1), dist_y(0, W - 1), dist_val(0, mint::mod() - 1);

    for (int i = 0; i < Q; ++i) {
        int l = dist_x(rng), r = dist_x(rng);
        if (l > r) std::swap(l, r);
        int d = dist_y(rng), u = dist_y(rng);
        if (d > u) std::swap(d, u);
        if (rng() & 1) {
            int val = dist_val(rng);
            queries[i] = { l, r, d, u, val };
            sol2.register_add_query_rectangle(l, r, d, u);
        } else {
            queries[i] = { l, r, d, u, -1 };
        }
    }
    sol2.build();

    for (const auto& [l, r, d, u, v] : queries) {
        if (v >= 0) {
            sol1.add(l, r, d, u, v), sol2.add(l, r, d, u, v);
        } else {
            assert(sol1.sum(l, r, d, u) == sol2.sum(l, r, d, u));
        }
    }
}

int main() {
    random_test<1000, 1000, 2000>();
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page