cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/LC/point_add_rectangle_sum/PointAddRectangleSum.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"

#include "../../../Src/Template/IOSetting.hpp"
#include "../../../Src/DataStructure/RectangleSum/PointAddRectangleSum.hpp"

#include <cassert>
#include <iostream>

using namespace zawa;

struct Point {
    using P = int;
    using W = long long;
    P x, y;
    W w;
};

struct Rect {
    using P = int;
    int l, d, r, u;
};

int main() {
    SetFastIO();
    int N, Q;
    std::cin >> N >> Q;
    PointAddRectangleSum<Point, Rect> solver;
    for (int i{} ; i < N ; i++) {
        int x, y, w;
        std::cin >> x >> y >> w;
        solver.add({x, y, w});
    }
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int x, y, w;
            std::cin >> x >> y >> w;
            solver.add({x, y, w});
        }
        else if (t == 1) {
            int l, d, r, u;
            std::cin >> l >> d >> r >> u;
            solver.product({l, d, r, u});
        }
        else {
            assert(false);
        }
    }
    for (auto ans : solver.execute()) {
        std::cout << ans << '\n';
    }
}
#line 1 "Test/LC/point_add_rectangle_sum/PointAddRectangleSum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/DataStructure/RectangleSum/PointAddRectangleSum.hpp"

#line 2 "Src/DataStructure/RectangleSum/RectangleSumOfPointCloud.hpp"

#line 4 "Src/DataStructure/RectangleSum/RectangleSumOfPointCloud.hpp"

#include <algorithm>
#include <concepts>
#include <utility>
#include <vector>
#include <type_traits>

namespace zawa {

namespace concepts {

template <class T>
concept Point = requires (T p) {
    typename T::P;
    typename T::W;
    { p.x } -> std::same_as<typename T::P&>;
    { p.y } -> std::same_as<typename T::P&>;
    { p.w } -> std::same_as<typename T::W&>;
};

template <class T>
concept Rectangle = requires (T r) {
    typename T::P;
    { r.l } -> std::same_as<typename T::P&>;
    { r.d } -> std::same_as<typename T::P&>;
    { r.r } -> std::same_as<typename T::P&>;
    { r.u } -> std::same_as<typename T::P&>;
};

template <class T, class U>
concept RSOPCQuery = Point<T> and Rectangle<U> and std::same_as<typename T::P, typename U::P>;

} // namespace concepts

template <class T, class U>
std::vector<typename T::W> RectangleSumOfPointCloud(std::vector<T> ps, std::vector<U> qs) requires concepts::RSOPCQuery<T, U> {
    using P = typename T::P;
    using W = typename T::W;
    usize n{ps.size()}, q{qs.size()};
    std::vector<P> xs(n);
    for (usize i{} ; i < n ; i++) xs[i] = ps[i].x;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    std::sort(ps.begin(), ps.end(), [&](const auto& L, const auto& R) -> bool {
            return L.y < R.y;
            });
    using Q = std::pair<P, usize>;
    std::vector<Q> query(qs.size() << 1);
    for (usize i{} ; i < qs.size() ; i++) {
        qs[i].l = (P)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), qs[i].l));
        qs[i].r = (P)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), qs[i].r));
        query[i] = std::pair{qs[i].d, i};
        query[i + q] = std::pair{qs[i].u, i + q};
    }
    std::sort(query.begin(), query.end());
    std::vector<W> fen(xs.size() + 1), res(qs.size());
    auto pref{[&](i32 r) -> W {
        W sum{};
        for ( ; r ; r -= r & -r) sum += fen[r];
        return sum;
    }};
    for (usize i{}, j{} ; i < query.size() ; i++) {
        while (j < n and ps[j].y < query[i].first) {
            i32 x{(i32)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), ps[j].x))}; 
            for ( x++ ; (usize)x < fen.size() ; x += x & -x) fen[x] += ps[j].w;
            j++;
        }
        usize idx{query[i].second};
        if (idx < q) {
            res[idx] += pref(qs[idx].l) - pref(qs[idx].r);
        }
        else {
            idx -= q;
            res[idx] += -pref(qs[idx].l) + pref(qs[idx].r);
        }
    } 
    return res;
}

} // namespace zawa
#line 5 "Src/DataStructure/RectangleSum/PointAddRectangleSum.hpp"

#include <cassert>
#line 9 "Src/DataStructure/RectangleSum/PointAddRectangleSum.hpp"

namespace zawa {

template <class T, class U>
requires concepts::RSOPCQuery<T, U>
class PointAddRectangleSum {
public:
    using P = typename T::P;
    using W = typename T::W;

    usize add(const T& P) {
        usize res{m_ps.size()};
        m_pos.emplace_back(false, res);
        m_ps.push_back(P);
        return res;
    }

    usize add(T&& P) {
        usize res{m_ps.size()};
        m_pos.emplace_back(false, res);
        m_ps.push_back(std::move(P));
        return res;
    }

    usize product(const U& Q) {
        usize res{m_qs.size()};
        m_pos.emplace_back(true, res);
        m_qs.push_back(Q);
        return res;
    }

    usize product(U&& Q) {
        usize res{m_qs.size()};
        m_pos.emplace_back(true, res);
        m_qs.push_back(std::move(Q));
        return res;
    }

    std::vector<W> execute() const {
        std::vector<W> res(m_qs.size());

        auto rec{[&](auto rec, usize l, usize r) -> void {
            assert(l <= r);
            if (l + 1 >= r) return;
            if (r - l > THRESHOLD) {
                usize m{(l + r) >> 1};
                rec(rec, l, m);
                rec(rec, m, r);
                std::vector<usize> p, q;
                for (usize i{l} ; i < m ; i++) if (!m_pos[i].first) {
                    p.push_back(m_pos[i].second);
                }
                for (usize i{m} ; i < r ; i++) if (m_pos[i].first) {
                    q.push_back(m_pos[i].second);
                }
                if (p.empty() or q.empty()) return;
                std::vector<W> kiyo{RectangleSumOfPointCloud<T, U>(
                        std::vector<T>(m_ps.begin() + p.front(), m_ps.begin() + p.back() + 1),
                        std::vector<U>(m_qs.begin() + q.front(), m_qs.begin() + q.back() + 1)
                        )};
                for (usize i{} ; i < q.size() ; i++) {
                    res[q[i]] += kiyo[i];
                }
            }
            else {
                for (usize i{l} ; i < r ; i++) if (m_pos[i].first) {
                    const U& u{m_qs[m_pos[i].second]};
                    for (usize j{l} ; j < i ; j++) if (!m_pos[j].first) {
                        const T& t{m_ps[m_pos[j].second]};
                        if (u.l <= t.x and t.x < u.r and u.d <= t.y and t.y < u.u) {
                            res[m_pos[i].second] += t.w;
                        }
                    }
                }
            }
        }};

        rec(rec, usize{0}, m_pos.size());
        return res;
    }

private:

    static constexpr usize THRESHOLD{200};

    std::vector<T> m_ps;
    std::vector<U> m_qs;
    std::vector<std::pair<bool, usize>> m_pos;
};

} // namespace zawa
#line 5 "Test/LC/point_add_rectangle_sum/PointAddRectangleSum.test.cpp"

#line 8 "Test/LC/point_add_rectangle_sum/PointAddRectangleSum.test.cpp"

using namespace zawa;

struct Point {
    using P = int;
    using W = long long;
    P x, y;
    W w;
};

struct Rect {
    using P = int;
    int l, d, r, u;
};

int main() {
    SetFastIO();
    int N, Q;
    std::cin >> N >> Q;
    PointAddRectangleSum<Point, Rect> solver;
    for (int i{} ; i < N ; i++) {
        int x, y, w;
        std::cin >> x >> y >> w;
        solver.add({x, y, w});
    }
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int x, y, w;
            std::cin >> x >> y >> w;
            solver.add({x, y, w});
        }
        else if (t == 1) {
            int l, d, r, u;
            std::cin >> l >> d >> r >> u;
            solver.product({l, d, r, u});
        }
        else {
            assert(false);
        }
    }
    for (auto ans : solver.execute()) {
        std::cout << ans << '\n';
    }
}
Back to top page