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: Static Rectangle Add Rectangle Sum
(library/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum.hpp)

Static Rectangle Add Rectangle Sum

$Q$ 個の矩形加算・矩形和取得クエリであって、取得クエリのあとに加算クエリが来ないような場合に $\Theta(Q)$ space, $\Theta(Q \log Q)$ time で処理します。ただし、クエリ先読みが可能であることを仮定します。

Depends on

Verified with

Code

#ifndef SUISEN_STATIC_RECTANGLE_ADD_RECTANGLE_SUM
#define SUISEN_STATIC_RECTANGLE_ADD_RECTANGLE_SUM

#include <algorithm>

#include "library/util/tuple_ops.hpp"
#include "library/datastructure/fenwick_tree/fenwick_tree.hpp"

namespace suisen {
    template <typename T>
    struct AddQuery {
        int l, r, d, u;
        T val;
        AddQuery() = default;
        AddQuery(int l, int r, int d, int u, const T &val) : l(l), r(r), d(d), u(u), val(val) {}
    };
    struct SumQuery {
        int l, r, d, u;
        SumQuery() = default;
        SumQuery(int l, int r, int d, int u) : l(l), r(r), d(d), u(u) {}
    };

    template <typename T>
    std::vector<T> static_rectangle_add_rectangle_sum(const std::vector<AddQuery<T>>& add_queries, const std::vector<SumQuery>& sum_queries) {
        using suffix_add_query_type = std::tuple<int, int, T>;         // l, d, val
        using prefix_sum_query_type = std::tuple<int, int, int, bool>; // r, u, query_id, sign

        std::vector<int> ys;
        std::vector<suffix_add_query_type> suf_add_queries;
        for (const auto& q : add_queries) {
            ys.push_back(q.d), ys.push_back(q.u);
            suf_add_queries.emplace_back(q.l, q.d, q.val), suf_add_queries.emplace_back(q.r, q.d, -q.val);
            suf_add_queries.emplace_back(q.l, q.u, -q.val), suf_add_queries.emplace_back(q.r, q.u, q.val);
        }

        std::sort(ys.begin(), ys.end());
        ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
        auto compress = [&ys](int y) -> int { return std::lower_bound(ys.begin(), ys.end(), y) - ys.begin(); };

        std::vector<prefix_sum_query_type> pre_sum_queries;
        for (std::size_t i = 0; i < sum_queries.size(); ++i) {
            const auto& q = sum_queries[i];
            pre_sum_queries.emplace_back(q.l, q.d, i, true), pre_sum_queries.emplace_back(q.r, q.d, i, false);
            pre_sum_queries.emplace_back(q.l, q.u, i, false), pre_sum_queries.emplace_back(q.r, q.u, i, true);
        }

        static constexpr auto x_comparator = [](const auto& q1, const auto& q2) { return std::get<0>(q1) < std::get<0>(q2); };
        std::sort(suf_add_queries.begin(), suf_add_queries.end(), x_comparator);
        std::sort(pre_sum_queries.begin(), pre_sum_queries.end(), x_comparator);

        using data_type = std::tuple<T, T, T, T>;
        FenwickTree<data_type> ft(ys.size());

        std::vector<T> res(sum_queries.size(), T{ 0 });
        const int n = suf_add_queries.size(), m = pre_sum_queries.size();
        for (int i = 0, j = 0; i < n or j < m;) {
            if (j == m or (i < n and std::get<0>(suf_add_queries[i]) < std::get<0>(pre_sum_queries[j]))) {
                const auto& [l, d, v] = suf_add_queries[i++];
                // v * (x - l) * (y - d) = v * xy - vd * x - vl * y + vld
                ft.add(compress(d), data_type{ v, -v * d, -v * l, v * l * d });
            } else {
                const auto& [x, y, qid, is_add] = pre_sum_queries[j++];
                auto [a, b, c, d] = ft.sum(0, compress(y));
                const T sum = a * x * y + b * x + c * y + d;
                if (is_add) res[qid] += sum;
                else        res[qid] -= sum;
            }
        }
        return res;
    }
} // namespace suisen


#endif // SUISEN_STATIC_RECTANGLE_ADD_RECTANGLE_SUM
#line 1 "library/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum.hpp"



#include <algorithm>

#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.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 8 "library/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum.hpp"

namespace suisen {
    template <typename T>
    struct AddQuery {
        int l, r, d, u;
        T val;
        AddQuery() = default;
        AddQuery(int l, int r, int d, int u, const T &val) : l(l), r(r), d(d), u(u), val(val) {}
    };
    struct SumQuery {
        int l, r, d, u;
        SumQuery() = default;
        SumQuery(int l, int r, int d, int u) : l(l), r(r), d(d), u(u) {}
    };

    template <typename T>
    std::vector<T> static_rectangle_add_rectangle_sum(const std::vector<AddQuery<T>>& add_queries, const std::vector<SumQuery>& sum_queries) {
        using suffix_add_query_type = std::tuple<int, int, T>;         // l, d, val
        using prefix_sum_query_type = std::tuple<int, int, int, bool>; // r, u, query_id, sign

        std::vector<int> ys;
        std::vector<suffix_add_query_type> suf_add_queries;
        for (const auto& q : add_queries) {
            ys.push_back(q.d), ys.push_back(q.u);
            suf_add_queries.emplace_back(q.l, q.d, q.val), suf_add_queries.emplace_back(q.r, q.d, -q.val);
            suf_add_queries.emplace_back(q.l, q.u, -q.val), suf_add_queries.emplace_back(q.r, q.u, q.val);
        }

        std::sort(ys.begin(), ys.end());
        ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
        auto compress = [&ys](int y) -> int { return std::lower_bound(ys.begin(), ys.end(), y) - ys.begin(); };

        std::vector<prefix_sum_query_type> pre_sum_queries;
        for (std::size_t i = 0; i < sum_queries.size(); ++i) {
            const auto& q = sum_queries[i];
            pre_sum_queries.emplace_back(q.l, q.d, i, true), pre_sum_queries.emplace_back(q.r, q.d, i, false);
            pre_sum_queries.emplace_back(q.l, q.u, i, false), pre_sum_queries.emplace_back(q.r, q.u, i, true);
        }

        static constexpr auto x_comparator = [](const auto& q1, const auto& q2) { return std::get<0>(q1) < std::get<0>(q2); };
        std::sort(suf_add_queries.begin(), suf_add_queries.end(), x_comparator);
        std::sort(pre_sum_queries.begin(), pre_sum_queries.end(), x_comparator);

        using data_type = std::tuple<T, T, T, T>;
        FenwickTree<data_type> ft(ys.size());

        std::vector<T> res(sum_queries.size(), T{ 0 });
        const int n = suf_add_queries.size(), m = pre_sum_queries.size();
        for (int i = 0, j = 0; i < n or j < m;) {
            if (j == m or (i < n and std::get<0>(suf_add_queries[i]) < std::get<0>(pre_sum_queries[j]))) {
                const auto& [l, d, v] = suf_add_queries[i++];
                // v * (x - l) * (y - d) = v * xy - vd * x - vl * y + vld
                ft.add(compress(d), data_type{ v, -v * d, -v * l, v * l * d });
            } else {
                const auto& [x, y, qid, is_add] = pre_sum_queries[j++];
                auto [a, b, c, d] = ft.sum(0, compress(y));
                const T sum = a * x * y + b * x + c * y + d;
                if (is_add) res[qid] += sum;
                else        res[qid] -= sum;
            }
        }
        return res;
    }
} // namespace suisen
Back to top page