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: Point Add Rectangle Sum
(Src/DataStructure/RectangleSum/PointAddRectangleSum.hpp)

概要

以下のようなクエリを処理する

  1. 二次元平面上に重み付きの点を追加する
  2. 矩形領域が与えられる。矩形領域の中にある点の重みの総和を求める

ただし、オフライン処理である。すなわち全てのクエリは処理前に与えられている必要がある。

ライブラリの使い方

template <class T, class U>
requires concepts::RSOPCQuery
PointAddRectangleSum()

T

点の型

Tは基本的には以下をコピれば問題無いはず。

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

Pは符号付き整数であることが期待される。

P型のメンバ変数x, yとW型のメンバ変数wが必要。

U

矩形領域型

基本的には以下をコピれば問題無い。Pが座標の型を表す。

// [l, r)x[d, u)
struct Rect {
    using P = int;
    int l, d, r, u;
};

Pは座標の型、psのPと型が一致している必要がある。

メンバ変数l, d, r, uが必要。左下の点が $(l, d)$ 、右上の点が $(r, u)$ となるようにする。

アルゴリズム

クエリ分割統治する。 $l$ 番目から $r - 1$ 番目のクエリを処理することを考える。 $m = \lfloor \frac{l+r}{2}\rfloor$ とする。

分割統治を考えているわけだから、結局の所 $m$ 番目から $r - 1$ 番目のクエリに含まれる求値に対する $l$ 番目から $m - 1$ 番目のクエリに含まれる点の寄与を計算できれば良い。

これはStatic Point Add Rectangle Sumそのものである。

Static verはlog1つでできて、各クエリは高々 $\Theta (\log Q)$ 計算されるので、log2つ。

実装上は $r - l$ がある程度小さかったら再帰を打ち切って愚直を回している。この工夫でほんのちょっと早くなった。

アルゴリズム・実装共に ei1333の日記 を参考にした。

Depends on

Verified with

Code

#pragma once

#include "./RectangleSumOfPointCloud.hpp"
#include "../../Template/TypeAlias.hpp"

#include <cassert>
#include <utility>
#include <vector>

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 2 "Src/DataStructure/RectangleSum/PointAddRectangleSum.hpp"

#line 2 "Src/DataStructure/RectangleSum/RectangleSumOfPointCloud.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/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
Back to top page