cp-library-cpp

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

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

:heavy_check_mark: Rectangle Add Rectangle Sum
(library/datastructure/fenwick_tree/rectangle_add_rectangle_sum.hpp)

Rectangle Add Rectangle Sum

$Q$ 個の矩形加算・矩形和取得クエリを $\Theta(Q\log Q)$ space, $\Theta(Q (\log Q) ^ 2)$ time で処理します。ただし、クエリ先読みが可能であることを仮定します。

Depends on

Verified with

Code

#ifndef SUISEN_RECTANGLE_ADD_RECTANGLE_SUM
#define SUISEN_RECTANGLE_ADD_RECTANGLE_SUM

#include "library/util/tuple_ops.hpp"
#include "library/datastructure/fenwick_tree/fenwick_tree_2d_sparse.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

#endif // SUISEN_RECTANGLE_ADD_RECTANGLE_SUM
#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
Back to top page