This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/datastructure/fenwick_tree/rectangle_add_rectangle_sum.hpp"
$Q$ 個の矩形加算・矩形和取得クエリを $\Theta(Q\log Q)$ space, $\Theta(Q (\log Q) ^ 2)$ time で処理します。ただし、クエリ先読みが可能であることを仮定します。
#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