Static Rectangle Add Point Get (other/static-rectangle-add-point-get.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-08-10 03:11:07+09:00
• Include: #include "other/static-rectangle-add-point-get.hpp"

2 次元平面上に重み付きの長方形が与えられます。

ある点を含む長方形の重みの総和を求めるいくつかのクエリに答えます。

コンストラクタ

(1) StaticRectangleAddPointGet< T, C >()
(2) StaticRectangleAddPointGet< T, C >(int n, int q)

T は座標が収まる型、C は重みの総和が収まる型を指定してください。

(2) で長方形の個数 $n$、クエリの個数 $q$ を指定した場合、領域を reserve するので少しだけ効率的です。

add_rectangle

void add_rectangle(T l, T d, T r, T u, C w)

$\lbrace (x,y):l \leq x \lt r, d \leq y \lt u\rbrace$ で表される重み $w$ の長方形を追加します。

制約

• $l \lt r$
• $d \lt u$

計算量

• $O(1)$

add_query

void add_query(T x, T y)

$(x, y)$ を含む長方形の重みの総和を求めるクエリを追加します。

計算量

• $O(1)$

calculate_queries

vector<C> calculate_queries() const

それぞれのクエリの答えを返します。$i$ 番目の要素は $i$ 番目に追加したクエリの答えが格納されます。

計算量

• $O((n + q) \log (n + q))$

Depends on

• Binary Indexed Tree (structure/others/binary-indexed-tree.hpp)

Required by

• Dynamic Rectangle Add Point Get (other/dynamic-rectangle-add-point-get.hpp)

Verified with

• test/verify/yosupo-rectangle-add-point-get.test.cpp

Code

#include "../structure/others/binary-indexed-tree.hpp"

template <typename T, typename C>
struct StaticRectangleAddPointGet {
 private:
  using BIT = BinaryIndexedTree<C>;

  static_assert(is_integral<T>::value,
                "template parameter T must be integral type");

  struct Rectangle {
    T l, d, r, u;
    C w;
  };

  struct Query {
    T x, y;
  };

  vector<Rectangle> rectangles;
  vector<Query> queries;

 public:
  StaticRectangleAddPointGet() = default;

  explicit StaticRectangleAddPointGet(int n, int q) {
    rectangles.reserve(n);
    queries.reserve(q);
  }

  void add_rectangle(T l, T d, T r, T u, C w) {
    rectangles.emplace_back(Rectangle{l, d, r, u, w});
  }

  void add_query(T x, T y) { queries.emplace_back(Query{x, y}); }

  vector<C> calculate_queries() const {
    int n = (int)rectangles.size();
    int q = (int)queries.size();
    vector<C> ans(q);
    if (rectangles.empty() or queries.empty()) {
      return ans;
    }

    vector<T> ys;
    ys.reserve(q);
    for (int i = 0; i < q; i++) {
      ys.emplace_back(queries[i].y);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    struct R {
      T x;
      int d, u;
      bool type;
      C w;
    };
    vector<R> rs;
    rs.reserve(n + n);
    for (int i = 0; i < n; i++) {
      auto &rect = rectangles[i];
      int d = lower_bound(ys.begin(), ys.end(), rect.d) - ys.begin();
      int u = lower_bound(ys.begin(), ys.end(), rect.u) - ys.begin();
      rs.emplace_back(R{rect.l, d, u, false, rect.w});
      rs.emplace_back(R{rect.r, d, u, true, rect.w});
    }
    sort(rs.begin(), rs.end(),
         [](const R &a, const R &b) { return a.x < b.x; });

    vector<int> qs(q);
    iota(qs.begin(), qs.end(), 0);
    sort(qs.begin(), qs.end(),
         [&](int a, int b) { return queries[a].x < queries[b].x; });

    int j = 0;
    BIT bit(ys.size());
    for (auto &i : qs) {
      while (j < n + n and rs[j].x <= queries[i].x) {
        if (rs[j].type) {
          bit.apply(rs[j].d, -rs[j].w);
          bit.apply(rs[j].u, +rs[j].w);
        } else {
          bit.apply(rs[j].d, rs[j].w);
          bit.apply(rs[j].u, -rs[j].w);
        }
        ++j;
      }
      int y = lower_bound(ys.begin(), ys.end(), queries[i].y) - ys.begin();
      ans[i] = bit.prod(y + 1);
    }
    return ans;
  }
};

#line 1 "structure/others/binary-indexed-tree.hpp"
template <typename T>
struct BinaryIndexedTree {
 private:
  int n;
  vector<T> data;

 public:
  BinaryIndexedTree() = default;

  explicit BinaryIndexedTree(int n) : n(n) { data.assign(n + 1, T()); }

  explicit BinaryIndexedTree(const vector<T> &v)
      : BinaryIndexedTree((int)v.size()) {
    build(v);
  }

  void build(const vector<T> &v) {
    assert(n == (int)v.size());
    for (int i = 1; i <= n; i++) data[i] = v[i - 1];
    for (int i = 1; i <= n; i++) {
      int j = i + (i & -i);
      if (j <= n) data[j] += data[i];
    }
  }

  void apply(int k, const T &x) {
    for (++k; k <= n; k += k & -k) data[k] += x;
  }

  T prod(int r) const {
    T ret = T();
    for (; r > 0; r -= r & -r) ret += data[r];
    return ret;
  }

  T prod(int l, int r) const { return prod(r) - prod(l); }

  int lower_bound(T x) const {
    int i = 0;
    for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if (i + k <= n && data[i + k] < x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }

  int upper_bound(T x) const {
    int i = 0;
    for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if (i + k <= n && data[i + k] <= x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }
};
#line 2 "other/static-rectangle-add-point-get.hpp"

template <typename T, typename C>
struct StaticRectangleAddPointGet {
 private:
  using BIT = BinaryIndexedTree<C>;

  static_assert(is_integral<T>::value,
                "template parameter T must be integral type");

  struct Rectangle {
    T l, d, r, u;
    C w;
  };

  struct Query {
    T x, y;
  };

  vector<Rectangle> rectangles;
  vector<Query> queries;

 public:
  StaticRectangleAddPointGet() = default;

  explicit StaticRectangleAddPointGet(int n, int q) {
    rectangles.reserve(n);
    queries.reserve(q);
  }

  void add_rectangle(T l, T d, T r, T u, C w) {
    rectangles.emplace_back(Rectangle{l, d, r, u, w});
  }

  void add_query(T x, T y) { queries.emplace_back(Query{x, y}); }

  vector<C> calculate_queries() const {
    int n = (int)rectangles.size();
    int q = (int)queries.size();
    vector<C> ans(q);
    if (rectangles.empty() or queries.empty()) {
      return ans;
    }

    vector<T> ys;
    ys.reserve(q);
    for (int i = 0; i < q; i++) {
      ys.emplace_back(queries[i].y);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    struct R {
      T x;
      int d, u;
      bool type;
      C w;
    };
    vector<R> rs;
    rs.reserve(n + n);
    for (int i = 0; i < n; i++) {
      auto &rect = rectangles[i];
      int d = lower_bound(ys.begin(), ys.end(), rect.d) - ys.begin();
      int u = lower_bound(ys.begin(), ys.end(), rect.u) - ys.begin();
      rs.emplace_back(R{rect.l, d, u, false, rect.w});
      rs.emplace_back(R{rect.r, d, u, true, rect.w});
    }
    sort(rs.begin(), rs.end(),
         [](const R &a, const R &b) { return a.x < b.x; });

    vector<int> qs(q);
    iota(qs.begin(), qs.end(), 0);
    sort(qs.begin(), qs.end(),
         [&](int a, int b) { return queries[a].x < queries[b].x; });

    int j = 0;
    BIT bit(ys.size());
    for (auto &i : qs) {
      while (j < n + n and rs[j].x <= queries[i].x) {
        if (rs[j].type) {
          bit.apply(rs[j].d, -rs[j].w);
          bit.apply(rs[j].u, +rs[j].w);
        } else {
          bit.apply(rs[j].d, rs[j].w);
          bit.apply(rs[j].u, -rs[j].w);
        }
        ++j;
      }
      int y = lower_bound(ys.begin(), ys.end(), queries[i].y) - ys.begin();
      ans[i] = bit.prod(y + 1);
    }
    return ans;
  }
};

Back to top page