verify/yosupo/yosupo-rectangle_sum-offline-2d-bit.test.cpp

• View this file on GitHub
• Last update: 2022-07-24 00:24:04-04:00
• Problem: https://judge.yosupo.jp/problem/rectangle_sum

Depends on

• library/contest/template-minimal.hpp
• Offline 2D BIT (library/data-structures/2d-range-queries/offline-2d-binary-indexed-tree.hpp)
• library/misc/easy-io.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/misc/easy-io.hpp"
#include "../../library/data-structures/2d-range-queries/offline-2d-binary-indexed-tree.hpp"

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	vector<int> xs, ys;
	vector<array<int, 3>> pts(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> pts[i][j];
		}
		xs.push_back(pts[i][0]);
		ys.push_back(pts[i][1]);
	}
	vector<array<int, 4>> qs(q);
	for (int i = 0; i < q; ++i) {
		cin >> qs[i][0] >> qs[i][2] >> qs[i][1] >> qs[i][3];
		--qs[i][1];
		--qs[i][3];
		xs.push_back(qs[i][0]);
		xs.push_back(qs[i][1]);
		ys.push_back(qs[i][2]);
		ys.push_back(qs[i][3]);
	}
	auto duplicates = [&](vector<int>& v) {
		sort(v.begin(), v.end());
		v.resize(unique(v.begin(), v.end()) - v.begin());
	};
	duplicates(xs);
	duplicates(ys);
	auto get = [&](vector<int> &v, int x) {
		return lower_bound(v.begin(), v.end(), x) - v.begin();
	};	
	Offline2DBIT<long long> O;
	for (int i = 0; i < n; ++i) {
		O.update(get(xs, pts[i][0]), get(ys, pts[i][1]), pts[i][2]);
	}
	O.init(xs.size() + 5);
	for (int i = 0; i < n; ++i) {
		O.update(get(xs, pts[i][0]), get(ys, pts[i][1]), pts[i][2]);
	}
	for (int i = 0; i < q; ++i) {
		cout << O.query(get(xs, qs[i][0]), get(xs, qs[i][1]), get(ys, qs[i][2]), get(ys, qs[i][3])) << '\n';
	}
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

inline namespace Helpers {
	//////////// is_iterable

	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable

	// this gets used only when we can call begin() and end() on that type

	template <class T, class = void> struct is_iterable : false_type {};
	template <class T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
									  decltype(end(declval<T>()))
									 >
						   > : true_type {};
	template <class T> constexpr bool is_iterable_v = is_iterable<T>::value;

	//////////// is_readable

	template <class T, class = void> struct is_readable : false_type {};
	template <class T> struct is_readable<T,
			typename std::enable_if_t<
				is_same_v<decltype(cin >> declval<T&>()), istream&>
			>
		> : true_type {};
	template <class T> constexpr bool is_readable_v = is_readable<T>::value;

	//////////// is_printable

	// // https://nafe.es/posts/2020-02-29-is-printable/

	template <class T, class = void> struct is_printable : false_type {};
	template <class T> struct is_printable<T,
			typename std::enable_if_t<
				is_same_v<decltype(cout << declval<T>()), ostream&>
			>
		> : true_type {};
	template <class T> constexpr bool is_printable_v = is_printable<T>::value;
}

inline namespace Input {
	template <class T> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
	template <class T, class... U> void re(T& t, U&... u);
	template <class T, class U> void re(pair<T, U>& p); // pairs


	// re: read

	template <class T> typename enable_if<is_readable_v<T>, void>::type re(T& x) { cin >> x; } // default

	template <class T> void re(complex<T>& c) { T a, b; re(a, b); c = {a, b}; } // complex

	template <class T> typename enable_if<needs_input_v<T>, void>::type re(T& i); // ex. vectors, arrays

	template <class T, class U> void re(pair<T, U>& p) { re(p.first, p.second); }
	template <class T> typename enable_if<needs_input_v<T>, void>::type re(T& i) {
		for (auto& x : i) re(x); }
	template <class T, class... U> void re(T& t, U&... u) { re(t); re(u...); } // read multiple


	// rv: resize and read vectors

	void rv(std::size_t) {}
	template <class T, class... U> void rv(std::size_t N, vector<T>& t, U&... u);
	template <class...U> void rv(std::size_t, std::size_t N2, U&... u);
	template <class T, class... U> void rv(std::size_t N, vector<T>& t, U&... u) {
		t.resize(N); re(t);
		rv(N, u...); }
	template <class...U> void rv(std::size_t, std::size_t N2, U&... u) {
		rv(N2, u...); }

	// dumb shortcuts to read in ints

	void decrement() {} // subtract one from each

	template <class T, class... U> void decrement(T& t, U&... u) { --t; decrement(u...); }
	#define ints(...) int __VA_ARGS__; re(__VA_ARGS__);
	#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
}
  
inline namespace ToString {
	template <class T> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

	// ts: string representation to print

	template <class T> typename enable_if<is_printable_v<T>, string>::type ts(T v) {
		stringstream ss; ss << fixed << setprecision(15) << v;
		return ss.str(); } // default

	template <class T> string bit_vec(T t) { // bit vector to string

		string res = "{"; for (int i = 0; i < (int)t.size(); ++i) res += ts(t[i]);
		res += "}"; return res; }
	string ts(vector<bool> v) { return bit_vec(v); }
	template <std::size_t SZ> string ts(bitset<SZ> b) { return bit_vec(b); } // bit vector

	template <class T, class U> string ts(pair<T, U> p); // pairs

	template <class T> typename enable_if<needs_output_v<T>, string>::type ts(T v); // vectors, arrays

	template <class T, class U> string ts(pair<T, U> p) { return "(" + ts(p.first) + ", " + ts(p.second) + ")"; }
	template <class T> typename enable_if<is_iterable_v<T>, string>::type ts_sep(T v, string sep) { 
		// convert container to string w/ separator sep

		bool fst = 1; string res = "";
		for (const auto& x : v) { 
			if (!fst) res += sep;
			fst = 0; res += ts(x);
		}
		return res;
	}
	template <class T> typename enable_if<needs_output_v<T>, string>::type ts(T v) {
		return "{" + ts_sep(v, ", ") + "}"; } 

	// for nested DS

	template <int, class T> typename enable_if<!needs_output_v<T>, vector<string>>::type 
	  ts_lev(const T& v) { return {ts(v)}; }
	template <int lev, class T> typename enable_if<needs_output_v<T>, vector<string>>::type 
	  ts_lev(const T& v) {
		if (lev == 0 || !(int)v.size()) return {ts(v)};
		vector<string> res;
		for (const auto& t : v) {
			if ((int)res.size()) res.back() += ",";
			vector<string> tmp = ts_lev<lev - 1>(t);
			res.insert(res.end(), tmp.begin(), tmp.end()); 
		}
		for (int i = 0; i < (int)res.size(); ++i) {
			string bef = " "; if (i == 0) bef = "{";
			res[i] = bef + res[i];
		}
		res.back() += "}";
		return res;
	}
}

inline namespace Output {
	template <class T> void pr_sep(ostream& os, string, const T& t) { os << ts(t); }
	template <class T, class... U> void pr_sep(ostream& os, string sep, const T& t, const U&... u) {
		pr_sep(os, sep, t); os << sep; pr_sep(os, sep, u...); }
	// print w/ no spaces

	template <class... T> void pr(const T&... t) { pr_sep(cout, "", t...); } 
	// print w/ spaces, end with newline

	void ps() { cout << "\n"; }
	template <class... T> void ps(const T&... t) { pr_sep(cout, " ", t...); ps(); } 
	// debug to cerr

	template <class... T> void dbg_out(const T&... t) {
		pr_sep(cerr, " | ", t...); cerr << endl; }
	void loc_info(int line, string names) {
		cerr << "Line(" << line << ") -> [" << names << "]: "; }
	template <int lev, class T> void dbgl_out(const T& t) {
		cerr << "\n\n" << ts_sep(ts_lev<lev>(t), "\n") << "\n" << endl; }
	#ifdef LOCAL
		#define dbg(...) loc_info(__LINE__, #__VA_ARGS__), dbg_out(__VA_ARGS__)
		#define dbgl(lev, x) loc_info(__LINE__, #x), dbgl_out<lev>(x)
	#else // don't actually submit with this
		#define dbg(...) 0
		#define dbgl(lev, x) 0
	#endif
}

inline namespace FileIO {
	void set_in(string s)  { (void)!freopen(s.c_str(), "r", stdin); }
	void set_out(string s) { (void)!freopen(s.c_str(), "w", stdout); }
	void set_io(string s = "") {
		cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams

		// cin.exceptions(cin.failbit);

		// throws exception when do smth illegal

		// ex. try to read letter into int

		if (!s.empty()) set_in(s + ".in"), set_out(s + ".out"); // for old USACO

	}
}

/**
 * x \in [0, sz)
 * y \in [0, sz)
 * First do all the updates, then call init
 * Afterwards, do the updates again, and now you can mix in the queries too
 */

template <class T> struct Offline2DBIT { 
	bool mode = false; // mode = 1 -> initialized

	int sz;
	std::vector<std::pair<int, int>> todo;
	std::vector<int> cnt, st, val;
	std::vector<T> bit;

	void init(int sz_) {
		sz = sz_;
		sz++;
		cnt.assign(sz, 0);
		st.assign(sz, 0);
		assert(!mode); mode = 1;
		std::vector<int> lst(sz, 0);
		cnt.assign(sz, 0);
		sort(todo.begin(), todo.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) { 
			return a.second < b.second; });
		for (auto& t : todo) 
			for (int x = t.first; x < sz; x += x & -x)
				if (lst[x] != t.second)
					lst[x] = t.second, cnt[x]++;
		int sum = 0; 
		for (int i = 0; i < sz; i++)
			lst[i] = 0, st[i] = (sum += cnt[i]);
		val.resize(sum); bit.resize(sum);
		reverse(todo.begin(), todo.end());
		for (auto& t : todo) 
			for (int x = t.first; x < sz; x += x & -x)
				if (lst[x] != t.second)
					lst[x] = t.second, val[--st[x]] = t.second;
	}

	int rank(int y, int l, int r) {
		return std::upper_bound(val.begin() + l, val.begin() + r, y) - val.begin() - l;
	}

	void inner_update(int x, int y, T t) {
		for (y = rank(y, st[x], st[x] + cnt[x]); y <= cnt[x]; y += y & -y)
			bit[st[x] + y - 1] += t;
	}

	void update(int x, int y, T t) {
		x++, y++;
		if (!mode) todo.push_back({x, y});
		else 
			for (; x < sz; x += x & -x)
				inner_update(x, y, t);
	}

	T inner_query(int x, int y) {
		T res = 0;
		for (y = rank(y, st[x], st[x] + cnt[x]); y; y -= y & -y)
			res += bit[st[x] + y - 1];
		return res;
	}

	T query(int x, int y) {
		x++, y++;
		assert(mode);
		T res = 0;
		for (; x; x -= x & -x) 
			res += inner_query(x, y);
		return res;
	}
	
	T query(int xl, int xr, int yl, int yr) {
		return query(xr, yr) - query(xl - 1, yr) - query(xr, yl - 1) + query(xl - 1, yl - 1);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	vector<int> xs, ys;
	vector<array<int, 3>> pts(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> pts[i][j];
		}
		xs.push_back(pts[i][0]);
		ys.push_back(pts[i][1]);
	}
	vector<array<int, 4>> qs(q);
	for (int i = 0; i < q; ++i) {
		cin >> qs[i][0] >> qs[i][2] >> qs[i][1] >> qs[i][3];
		--qs[i][1];
		--qs[i][3];
		xs.push_back(qs[i][0]);
		xs.push_back(qs[i][1]);
		ys.push_back(qs[i][2]);
		ys.push_back(qs[i][3]);
	}
	auto duplicates = [&](vector<int>& v) {
		sort(v.begin(), v.end());
		v.resize(unique(v.begin(), v.end()) - v.begin());
	};
	duplicates(xs);
	duplicates(ys);
	auto get = [&](vector<int> &v, int x) {
		return lower_bound(v.begin(), v.end(), x) - v.begin();
	};	
	Offline2DBIT<long long> O;
	for (int i = 0; i < n; ++i) {
		O.update(get(xs, pts[i][0]), get(ys, pts[i][1]), pts[i][2]);
	}
	O.init(xs.size() + 5);
	for (int i = 0; i < n; ++i) {
		O.update(get(xs, pts[i][0]), get(ys, pts[i][1]), pts[i][2]);
	}
	for (int i = 0; i < q; ++i) {
		cout << O.query(get(xs, qs[i][0]), get(xs, qs[i][1]), get(ys, qs[i][2]), get(ys, qs[i][3])) << '\n';
	}
	return 0;
}

Back to top page