library

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

View the Project on GitHub Harui-i/library

:heavy_check_mark: test/verify/structure/yosupo-rectangle-add-point-get.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_add_point_get"
#include "template/template.hpp"
#include "structure/rectangle_apply_point_get.hpp"

#include <algorithm>
#include <vector>

ll composition(ll f, ll g) {
  return f + g;
}

ll id() {
  return 0;
}

struct Rect {
  int l, d, r, u;
  ll w;
};

struct Query {
  int type;
  Rect rect;
  int x, y;
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int N, Q; cin >> N >> Q;
  vector<Rect> rects(N);
  for (int i=0; i<N; i++) {
    cin >> rects[i].l >> rects[i].d >> rects[i].r >> rects[i].u >> rects[i].w;
  }

  vector<Query> qs(Q);
  vector<int> xs, ys;
  for (int q=0; q<Q; q++) {
    cin >> qs[q].type;
    if (qs[q].type == 0) {
      cin >> qs[q].rect.l >> qs[q].rect.d >> qs[q].rect.r >> qs[q].rect.u >> qs[q].rect.w;
    }
    else {
      cin >> qs[q].x >> qs[q].y;
      xs.push_back(qs[q].x);
      ys.push_back(qs[q].y);
    }
  }

  if (xs.empty()) return 0;

  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  sort(ys.begin(), ys.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());

  auto get_x = [&](int x) {
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
  };
  auto get_y = [&](int y) {
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
  };
  auto apply = [&](rectangle_apply_point_get<ll, composition, id>& g, const Rect& rect) {
    int l = get_x(rect.l);
    int r = get_x(rect.r);
    int d = get_y(rect.d);
    int u = get_y(rect.u);
    g.apply(l, r, d, u, rect.w);
  };

  rectangle_apply_point_get<ll, composition, id> g(0, (int)xs.size(), 0, (int)ys.size());
  for (auto& rect : rects) apply(g, rect);

  for (auto& q : qs) {
    if (q.type == 0) {
      apply(g, q.rect);
    }
    else {
      cout << g.get(get_x(q.x), get_y(q.y)) << "\n";
    }
  }

  return 0;
}
#line 1 "test/verify/structure/yosupo-rectangle-add-point-get.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_add_point_get"
#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 1 "structure/rectangle_apply_point_get.hpp"



#line 5 "structure/rectangle_apply_point_get.hpp"
#include <vector>

template <class F, F (*composition)(F, F), F (*id)(), class T = int>
struct rectangle_apply_point_get {
  rectangle_apply_point_get(T xl, T xr, T yl, T yr)
      : xl(xl), xr(xr), yl(yl), yr(yr), root(-1) {
    assert(xl < xr);
    assert(yl < yr);
    root = new_x_node();
  }

  void apply(T l, T r, T d, T u, F f) {
    assert(xl <= l && l <= r && r <= xr);
    assert(yl <= d && d <= u && u <= yr);
    apply_x(root, xl, xr, l, r, d, u, f);
  }

  F get(T x, T y) const {
    assert(xl <= x && x < xr);
    assert(yl <= y && y < yr);
    return get_x(root, xl, xr, x, y);
  }

private:
  struct XNode {
    int left, right, y_root;
  };

  struct YNode {
    int left, right;
    F val;
  };

  int new_x_node() {
    xs.push_back({-1, -1, -1});
    return (int)xs.size() - 1;
  }

  int new_y_node() {
    ys.push_back({-1, -1, id()});
    return (int)ys.size() - 1;
  }

  void apply_x(int k, T nl, T nr, T ql, T qr, T qd, T qu, F f) {
    if (qr <= nl || nr <= ql) return;
    if (ql <= nl && nr <= qr) {
      xs[k].y_root = apply_y(xs[k].y_root, yl, yr, qd, qu, f);
      return;
    }

    T mid = nl + (nr - nl) / 2;
    if (ql < mid) {
      if (xs[k].left == -1) {
        int child = new_x_node();
        xs[k].left = child;
      }
      apply_x(xs[k].left, nl, mid, ql, qr, qd, qu, f);
    }
    if (mid < qr) {
      if (xs[k].right == -1) {
        int child = new_x_node();
        xs[k].right = child;
      }
      apply_x(xs[k].right, mid, nr, ql, qr, qd, qu, f);
    }
  }

  int apply_y(int k, T nl, T nr, T ql, T qr, F f) {
    if (qr <= nl || nr <= ql) return k;
    if (k == -1) k = new_y_node();
    if (ql <= nl && nr <= qr) {
      ys[k].val = composition(f, ys[k].val);
      return k;
    }

    T mid = nl + (nr - nl) / 2;
    if (ql < mid) ys[k].left = apply_y(ys[k].left, nl, mid, ql, qr, f);
    if (mid < qr) ys[k].right = apply_y(ys[k].right, mid, nr, ql, qr, f);
    return k;
  }

  F get_x(int k, T nl, T nr, T x, T y) const {
    if (k == -1) return id();

    F res = get_y(xs[k].y_root, yl, yr, y);
    if (nr - nl == 1) return res;

    T mid = nl + (nr - nl) / 2;
    if (x < mid) return composition(get_x(xs[k].left, nl, mid, x, y), res);
    return composition(get_x(xs[k].right, mid, nr, x, y), res);
  }

  F get_y(int k, T nl, T nr, T y) const {
    if (k == -1) return id();

    F res = ys[k].val;
    if (nr - nl == 1) return res;

    T mid = nl + (nr - nl) / 2;
    if (y < mid) return composition(get_y(ys[k].left, nl, mid, y), res);
    return composition(get_y(ys[k].right, mid, nr, y), res);
  }

  T xl, xr, yl, yr;
  int root;
  std::vector<XNode> xs;
  std::vector<YNode> ys;
};


#line 4 "test/verify/structure/yosupo-rectangle-add-point-get.test.cpp"

#include <algorithm>
#line 7 "test/verify/structure/yosupo-rectangle-add-point-get.test.cpp"

ll composition(ll f, ll g) {
  return f + g;
}

ll id() {
  return 0;
}

struct Rect {
  int l, d, r, u;
  ll w;
};

struct Query {
  int type;
  Rect rect;
  int x, y;
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int N, Q; cin >> N >> Q;
  vector<Rect> rects(N);
  for (int i=0; i<N; i++) {
    cin >> rects[i].l >> rects[i].d >> rects[i].r >> rects[i].u >> rects[i].w;
  }

  vector<Query> qs(Q);
  vector<int> xs, ys;
  for (int q=0; q<Q; q++) {
    cin >> qs[q].type;
    if (qs[q].type == 0) {
      cin >> qs[q].rect.l >> qs[q].rect.d >> qs[q].rect.r >> qs[q].rect.u >> qs[q].rect.w;
    }
    else {
      cin >> qs[q].x >> qs[q].y;
      xs.push_back(qs[q].x);
      ys.push_back(qs[q].y);
    }
  }

  if (xs.empty()) return 0;

  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  sort(ys.begin(), ys.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());

  auto get_x = [&](int x) {
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
  };
  auto get_y = [&](int y) {
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
  };
  auto apply = [&](rectangle_apply_point_get<ll, composition, id>& g, const Rect& rect) {
    int l = get_x(rect.l);
    int r = get_x(rect.r);
    int d = get_y(rect.d);
    int u = get_y(rect.u);
    g.apply(l, r, d, u, rect.w);
  };

  rectangle_apply_point_get<ll, composition, id> g(0, (int)xs.size(), 0, (int)ys.size());
  for (auto& rect : rects) apply(g, rect);

  for (auto& q : qs) {
    if (q.type == 0) {
      apply(g, q.rect);
    }
    else {
      cout << g.get(get_x(q.x), get_y(q.y)) << "\n";
    }
  }

  return 0;
}
Back to top page