Luzhiled's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub ei1333/library

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

2 次元平面上に重み付きの長方形を追加するクエリと、ある点を含む長方形の重みの総和を求めるいくつかのクエリに答えます。

コンストラクタ

(1) DynamicRectangleAddPointGet< T, C >()
(2) DynamicRectangleAddPointGet< T, C >(int q)

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

(2) でクエリの個数 $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$ の長方形を追加するクエリを追加します。

制約

計算量

add_query

void add_query(T x, T y)

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

計算量

calculate_queries

vector<C> calculate_queries() const

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

計算量

Depends on

Verified with

Code

#include "static-rectangle-add-point-get.hpp"

template <typename T, typename C>
struct DynamicRectangleAddPointGet {
 private:
  using StaticPointGetSolver = StaticRectangleAddPointGet<T, 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<variant<Rectangle, Query> > queries;

 public:
  DynamicRectangleAddPointGet() = default;

  explicit DynamicRectangleAddPointGet(int q) { queries.reserve(q); }

  void add_rectangle(T l, T d, T r, T u, C w) {
    queries.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 q = (int)queries.size();
    vector<int> rev(q);
    int sz = 0;
    for (int i = 0; i < q; i++) {
      if (holds_alternative<Query>(queries[i])) {
        rev[i] = sz++;
      }
    }
    vector<C> ans(sz);
    queue<pair<int, int> > range;
    range.emplace(0, q);
    while (not range.empty()) {
      auto [l, r] = range.front();
      range.pop();
      int m = (l + r) >> 1;
      StaticPointGetSolver solver;
      for (int k = l; k < m; k++) {
        if (holds_alternative<Rectangle>(queries[k])) {
          auto &rect = get<Rectangle>(queries[k]);
          solver.add_rectangle(rect.l, rect.d, rect.r, rect.u, rect.w);
        }
      }
      for (int k = m; k < r; k++) {
        if (holds_alternative<Query>(queries[k])) {
          auto &query = get<Query>(queries[k]);
          solver.add_query(query.x, query.y);
        }
      }
      auto sub = solver.calculate_queries();
      for (int k = m, t = 0; k < r; k++) {
        if (holds_alternative<Query>(queries[k])) {
          ans[rev[k]] += sub[t++];
        }
      }
      if (l + 1 < m) range.emplace(l, m);
      if (m + 1 < r) range.emplace(m, r);
    }
    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;
  }
};
#line 2 "other/dynamic-rectangle-add-point-get.hpp"

template <typename T, typename C>
struct DynamicRectangleAddPointGet {
 private:
  using StaticPointGetSolver = StaticRectangleAddPointGet<T, 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<variant<Rectangle, Query> > queries;

 public:
  DynamicRectangleAddPointGet() = default;

  explicit DynamicRectangleAddPointGet(int q) { queries.reserve(q); }

  void add_rectangle(T l, T d, T r, T u, C w) {
    queries.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 q = (int)queries.size();
    vector<int> rev(q);
    int sz = 0;
    for (int i = 0; i < q; i++) {
      if (holds_alternative<Query>(queries[i])) {
        rev[i] = sz++;
      }
    }
    vector<C> ans(sz);
    queue<pair<int, int> > range;
    range.emplace(0, q);
    while (not range.empty()) {
      auto [l, r] = range.front();
      range.pop();
      int m = (l + r) >> 1;
      StaticPointGetSolver solver;
      for (int k = l; k < m; k++) {
        if (holds_alternative<Rectangle>(queries[k])) {
          auto &rect = get<Rectangle>(queries[k]);
          solver.add_rectangle(rect.l, rect.d, rect.r, rect.u, rect.w);
        }
      }
      for (int k = m; k < r; k++) {
        if (holds_alternative<Query>(queries[k])) {
          auto &query = get<Query>(queries[k]);
          solver.add_query(query.x, query.y);
        }
      }
      auto sub = solver.calculate_queries();
      for (int k = m, t = 0; k < r; k++) {
        if (holds_alternative<Query>(queries[k])) {
          ans[rev[k]] += sub[t++];
        }
      }
      if (l + 1 < m) range.emplace(l, m);
      if (m + 1 < r) range.emplace(m, r);
    }
    return ans;
  }
};
Back to top page