test/verify/structure/yosupo-rectangle-sum.test.cpp

View this file on GitHub
Last update: 2026-01-24 17:34:48+09:00
Problem: https://judge.yosupo.jp/problem/rectangle_sum

Depends on

Code

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

#include <vector>

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N, Q; cin >> N >> Q;
  offline_2dsum<int, ll> g;
  for (int i=0; i<N; i++) {
    int x, y; cin >> x >> y;
    ll w; cin >> w;
    g.add_point(x, y, w);
  }

  for (int q=0; q<Q; q++) {
    int l, d, r, u;
    cin >> l >> d >> r >> u;
    g.add_query(l, r, d, u);
  }

  auto ans = g.solve();
  for (auto x : ans) cout << x << "\n";

  return 0;
}

#line 1 "test/verify/structure/yosupo-rectangle-sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
#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/offline_2dsum.hpp"



#include <vector>
#include <algorithm>
#line 1 "structure/fenwick_tree.hpp"



#line 6 "structure/fenwick_tree.hpp"

template <class T> struct fenwick_tree {
  fenwick_tree(): _n(0) {}
  explicit fenwick_tree(int n): _n(n), data(n) {}

  // point add
  void add(int p, T x) {
    assert(0 <= p && p < _n);
    p++;
    while (p <= _n) {
      data[p-1] += T(x);
      p += p & -p;
    }
  } 

  T sum(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    return sum(r) - sum(l);
  }

private:
  int _n;
  std::vector<T> data;
  T sum(int r) {
    T ret(0);
    while (r > 0) {
      ret += data[r-1];
      r -= r & -r;
    }

    return ret;
  }
};


#line 7 "structure/offline_2dsum.hpp"

template <class T, class W> struct offline_2dsum {
  struct Point {
    T x, y;
    W w;
  };
  struct Query {
    T l, r, d, u;
  };

  void add_point(T x, T y, W w) {
    points.push_back({x, y, w});
  }

  void add_query(T l, T r, T d, T u) {
    queries.push_back({l, r, d, u});
  }

  std::vector<W> solve() {
    int n = points.size();
    int q = queries.size();
    std::vector<W> res(q, 0);

    std::vector<T> ys;
    ys.reserve(n);
    for (auto& p : points) ys.push_back(p.y);
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());

    auto get_y = [&](T y) {
      return std::lower_bound(ys.begin(), ys.end(), y) - ys.begin();
    };

    struct Event {
      T x;
      int d, u;
      int id;
      int type; // -1 for l, 1 for r
      bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type < other.type;
      }
    };

    std::vector<Event> events;
    events.reserve(2 * q);
    for (int i = 0; i < q; i++) {
      int d = get_y(queries[i].d);
      int u = get_y(queries[i].u);
      events.push_back({queries[i].l, d, u, i, -1});
      events.push_back({queries[i].r, d, u, i, 1});
    }

    std::sort(events.begin(), events.end());
    std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
      return a.x < b.x;
    });

    fenwick_tree<W> ft(ys.size());
    int pi = 0;
    for (auto& e : events) {
      while (pi < n && points[pi].x < e.x) {
        ft.add(get_y(points[pi].y), points[pi].w);
        pi++;
      }
      res[e.id] += (W)e.type * ft.sum(e.d, e.u);
    }

    return res;
  }

private:
  std::vector<Point> points;
  std::vector<Query> queries;
};


#line 4 "test/verify/structure/yosupo-rectangle-sum.test.cpp"

#line 6 "test/verify/structure/yosupo-rectangle-sum.test.cpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N, Q; cin >> N >> Q;
  offline_2dsum<int, ll> g;
  for (int i=0; i<N; i++) {
    int x, y; cin >> x >> y;
    ll w; cin >> w;
    g.add_point(x, y, w);
  }

  for (int q=0; q<Q; q++) {
    int l, d, r, u;
    cin >> l >> d >> r >> u;
    g.add_query(l, r, d, u);
  }

  auto ans = g.solve();
  for (auto x : ans) cout << x << "\n";

  return 0;
}