This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum" #include <iostream> #include <tuple> #include "library/datastructure/fenwick_tree/fenwick_tree_2d_sparse.hpp" using suisen::FenwickTree2DSparse; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; FenwickTree2DSparse<long long> seg(n + q); std::vector<std::tuple<int, int, int>> init(n); for (int i = 0; i < n; ++i) { int x, y, w; std::cin >> x >> y >> w; init[i] = { x, y, w }; seg.add_point(x, y); } std::vector<std::tuple<int, int, int, int, int>> queries(q); for (int i = 0; i < q; ++i) { int t; std::cin >> t; if (t == 0) { int x, y, w; std::cin >> x >> y >> w; queries[i] = { t, x, y, w, 0 }; seg.add_point(x, y); } else { int l, d, r, u; std::cin >> l >> d >> r >> u; queries[i] = { t, l, r, d, u }; } } seg.build(); for (auto [x, y, w] : init) { seg.add(x, y, w); } for (const auto &q : queries) { if (std::get<0>(q) == 0) { auto [t, x, y, w, _] = q; seg.add(x, y, w); } else { auto [t, l, r, d, u] = q; std::cout << seg.sum(l, r, d, u) << '\n'; } } return 0; }
#line 1 "test/src/datastructure/fenwick_tree/fenwick_tree_2d_sparse/point_add_rectangle_sum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum" #include <iostream> #include <tuple> #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 7 "test/src/datastructure/fenwick_tree/fenwick_tree_2d_sparse/point_add_rectangle_sum.test.cpp" using suisen::FenwickTree2DSparse; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; FenwickTree2DSparse<long long> seg(n + q); std::vector<std::tuple<int, int, int>> init(n); for (int i = 0; i < n; ++i) { int x, y, w; std::cin >> x >> y >> w; init[i] = { x, y, w }; seg.add_point(x, y); } std::vector<std::tuple<int, int, int, int, int>> queries(q); for (int i = 0; i < q; ++i) { int t; std::cin >> t; if (t == 0) { int x, y, w; std::cin >> x >> y >> w; queries[i] = { t, x, y, w, 0 }; seg.add_point(x, y); } else { int l, d, r, u; std::cin >> l >> d >> r >> u; queries[i] = { t, l, r, d, u }; } } seg.build(); for (auto [x, y, w] : init) { seg.add(x, y, w); } for (const auto &q : queries) { if (std::get<0>(q) == 0) { auto [t, x, y, w, _] = q; seg.add(x, y, w); } else { auto [t, l, r, d, u] = q; std::cout << seg.sum(l, r, d, u) << '\n'; } } return 0; }