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/fenwick_tree_2d_sparse/rectangle_sum.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/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);
    std::vector<std::tuple<int, int, int>> points(n);
    for (int i = 0; i < n; ++i) {
        int x, y, w;
        std::cin >> x >> y >> w;
        points[i] = { x, y, w };
        seg.add_point(x, y);
    }
    seg.build();
    for (auto [x, y, w] : points) {
        seg.add(x, y, w);
    }
    for (int i = 0; i < q; ++i) {
        int l, d, r, u;
        std::cin >> l >> d >> r >> u;
        std::cout << seg.sum(l, r, d, u) << '\n';
    }
    return 0;
}
#line 1 "test/src/datastructure/fenwick_tree/fenwick_tree_2d_sparse/rectangle_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/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/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);
    std::vector<std::tuple<int, int, int>> points(n);
    for (int i = 0; i < n; ++i) {
        int x, y, w;
        std::cin >> x >> y >> w;
        points[i] = { x, y, w };
        seg.add_point(x, y);
    }
    seg.build();
    for (auto [x, y, w] : points) {
        seg.add(x, y, w);
    }
    for (int i = 0; i < q; ++i) {
        int l, d, r, u;
        std::cin >> l >> d >> r >> u;
        std::cout << seg.sum(l, r, d, u) << '\n';
    }
    return 0;
}
Back to top page