mmrz's library

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

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

verify/yosupo/area_of_union_of_rectangles.test.cpp

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Problem: https://judge.yosupo.jp/problem/area_of_union_of_rectangles

Depends on

• area_of_union_of_rectangles(長方形の和集合の面積) (data_structure/area_of_union_of_rectangles.hpp)
• 遅延セグメント木 (data_structure/lazy_segment_tree.hpp)
• template/template.hpp

Code

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

#include "./../../template/template.hpp"
#include "./../../data_structure/area_of_union_of_rectangles.hpp"

void mmrz::solve(){
	int n;
	cin >> n;
	vector<tuple<int, int, int, int>> rectangles(n);
	for(auto &[l, d, r, u] : rectangles)cin >> l >> d >> r >> u;

	cout << area_of_union_rectangles<int>(rectangles).solve<ll>() << '\n';
}

#line 1 "verify/yosupo/area_of_union_of_rectangles.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/area_of_union_of_rectangles"

#line 1 "template/template.hpp"
# include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double pi = acos(-1);
template<class T>constexpr T inf() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T hinf() { return inf<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); }
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); }
template<class T> bool chmin(T& a,T b) { if(a > b){a = b; return true;} return false; }
template<class T> bool chmax(T& a,T b) { if(a < b){a = b; return true;} return false; }
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(ll n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(ll n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
ll gcd(ll a, ll b) { if (b == 0)return a; return gcd(b, a%b); };
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g*b; };
ll MOD(ll x, ll m){return (x%m+m)%m; }
ll FLOOR(ll x, ll m) {ll r = (x%m+m)%m; return (x-r)/m; }
template<class T> using dijk = priority_queue<T, vector<T>, greater<T>>;
# define all(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        (wpwpw).erase(unique(all((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(all((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(all((rprpr)),(rprpr).begin(),TU<char>)
# define rep(i,upupu)         for(ll i = 0, i##_len = (upupu);(i) < (i##_len);(i)++)
# define reps(i,opopo)        for(ll i = 1, i##_len = (opopo);(i) <= (i##_len);(i)++)
# define len(x)                ((ll)(x).size())
# define bit(n)               (1LL << (n))
# define pb push_back
# define eb emplace_back
# define exists(c, e)         ((c).find(e) != (c).end())

struct INIT{
	INIT(){
		std::ios::sync_with_stdio(false);
		std::cin.tie(0);
		cout << fixed << setprecision(20);
	}
}INIT;

namespace mmrz {
	void solve();
}

int main(){
	mmrz::solve();
}
#line 2 "data_structure/area_of_union_of_rectangles.hpp"

#line 2 "data_structure/lazy_segment_tree.hpp"

#line 5 "data_structure/lazy_segment_tree.hpp"

template<class S, auto op, auto e, class F, auto mapping, auto composition, auto id>
struct lazy_segment_tree {
private:
	int n;
	int log;
	int size;
	std::vector<S> node;
	std::vector<F> lazy;

	void update(int k) { node[k] = op(node[2 * k], node[2 * k + 1]); }
	void all_apply(int k, F f) {
		node[k] = mapping(f, node[k]);
		if(k < size) lazy[k] = composition(f, lazy[k]);
	}
	void push(int k) {
		all_apply(2*k + 0, lazy[k]);
		all_apply(2*k + 1, lazy[k]);
		lazy[k] = id();
	}
public:
	lazy_segment_tree() : lazy_segment_tree(0) {}

	lazy_segment_tree(int _n) : lazy_segment_tree(std::vector<S>(_n, e())) {}

	lazy_segment_tree(const std::vector<S> &v) : n((int)v.size()) {
		size = 1;
		while(size < n) size <<= 1;

		log = __builtin_ctz(size);

		node.resize(2*size, e());
		lazy.resize(size, id());

		for(int i = 0;i < n;i++)node[i + size] = v[i];
		for(int i = size-1;i >= 1;i--)node[i] = op(node[2*i + 0], node[2*i + 1]);
	}

	void set(int x, S val) {
		assert(0 <= x && x < n);
		x += size;

		for(int i = log;i >= 1;i--)push(x >> i);
		node[x] = val;
		for(int i = 1;i <= log;i++)update(x >> i);
	}

	S operator[](int x) {
		assert(0 <= x && x < n);
		x += size;

		for(int i = log;i >= 1;i--)push(x >> i);
		return node[x];
	}

	S fold(int l, int r) {
		assert(0 <= l && l <= r && r <= n);
		if(l == r)return e();

		l += size;
		r += size;

		for(int i = log;i >= 1;i--) {
			if(((l >> i) << i) != l)push(l >> i);
			if(((r >> i) << i) != r)push((r-1) >> i);
		}

		S L = e(), R = e();
		for(;l < r;l >>= 1, r >>= 1){
			if(l&1)L = op(L, node[l++]);
			if(r&1)R = op(node[--r], R);
		}
		return op(L, R);
	}

	S all_fold() { return node[1]; };

	void apply(int x, F f) {
		assert(0 <= x && x < n);

		x += size;
		for(int i = log;i >= 1;i--)push(x >> i);
		node[x] = mapping(f, node[x]);
		for(int i = 1;i <= log;i++)update(x >> i);
	}

	void apply(int l, int r, F f) {
		assert(0 <= l && l <= r && r <= n);
		if(l == r)return;

		l += size;
		r += size;

		for(int i = log;i >= 1;i--) {
			if(((l >> i) << i) != l)push(l >> i);
			if(((r >> i) << i) != r)push((r-1) >> i);
		}

		{
			int l2 = l, r2 = r;
			while (l < r) {
				if (l & 1) all_apply(l++, f);
				if (r & 1) all_apply(--r, f);
				l >>= 1;
				r >>= 1;
			}
			l = l2;
			r = r2;
		}

		for (int i = 1; i <= log; i++) {
			if (((l >> i) << i) != l) update(l >> i);
			if (((r >> i) << i) != r) update((r - 1) >> i);
		}
	}

	template<bool (*g)(S)> int max_right(int l) {
		return max_right(l, [](S x){ return g(x); });
	}
	template<class G> int max_right(int l, G g) {
		assert(0 <= l && l <= n);
		assert(g(e()));

		if(l == n)return n;

		l += size;
		for(int i = log;i >= 1;i--)push(l >> i);

		S sum = e();
		do {
			while(l%2 == 0)l >>= 1;
			if(not g(op(sum, node[l]))) {
				while(l < size) {
					push(l);
					l <<= 1;
					if(g(op(sum, node[l]))) {
						sum = op(sum, node[l]);
						l++;
					}
				}
				return l-size;
			}
			sum = op(sum, node[l]);
			l++;
		}while((l&-l) != l);
		return n;
	}

	template <bool (*g)(S)> int min_left(int r) {
		return min_left(r, [](S x) { return g(x); });
	}
	template<class G> int min_left(int r, G g) {
		assert(0 <= r && r <= n);
		assert(g(e()));

		if(r == 0)return 0;

		r += size;
		for(int i = log;i >= 1;i--)push((r-1) >> i);

		S sum = e();
		do {
			r--;
			while(r > 1 && (r%2))r >>= 1;
			if(not g(op(node[r], sum))) {
				while(r < size) {
					push(r);
					r = r*2 + 1;
					if(g(op(node[r], sum))) {
						sum = op(node[r], sum);
						r--;
					}
				}
				return r+1-size;
			}
			sum = op(node[r], sum);
		}while((r&-r) != r);
		return 0;
	}
};
#line 4 "data_structure/area_of_union_of_rectangles.hpp"

#line 11 "data_structure/area_of_union_of_rectangles.hpp"

template<class T>
struct area_of_union_rectangles {
private:
	std::vector<T> ys;
	std::vector<std::tuple<T, int, int>> xs;
	std::vector<std::tuple<T, T, T, T>> rectangles;
	using S = std::pair<int, T>;
	using F = int;
	static S op(S a, S b){
		if(a.first < b.first)return a;
		if(a.first > b.first)return b;
		return std::make_pair(a.first, a.second+b.second);
	}
	static S e(){ return std::make_pair(std::numeric_limits<int>::max()/2, 0); }
	static S mapping(F f, S x){ return std::make_pair(x.first+f, x.second); }
	static F composition(F f, F g){ return f+g; }
	static F id(){ return 0; }
public:

	// l, d, r, u
	area_of_union_rectangles(std::vector<std::tuple<T, T, T, T>> _rectangles) : rectangles(_rectangles) {
		ys.reserve(rectangles.size()+rectangles.size());
		xs.reserve(rectangles.size()+rectangles.size());

		for(size_t i = 0;i < rectangles.size();i++){
			auto &[l, d, r, u] = rectangles[i];
			ys.emplace_back(d);
			ys.emplace_back(u);
			xs.emplace_back(l, i, 1);
			xs.emplace_back(r, i, -1);
		}

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

		std::map<T, int> y_compress;
		for(size_t i = 0;i < ys.size();i++){
			y_compress[ys[i]] = i;
		}
		for(size_t i = 0;i < rectangles.size();i++){
			auto &[l, d, r, u] = rectangles[i];
			u = y_compress[u];
			d = y_compress[d];
		}
	};

	template<typename U>
	U solve(){
		std::vector<S> vs((int)ys.size()-1);
		for(size_t i = 0;i+1 < ys.size();i++){
			vs[i] = std::make_pair(0, ys[i+1]-ys[i]);
		}
		lazy_segment_tree<S, op, e, F, mapping, composition, id> seg(vs);
		
		U ret = 0;

		T total = ys.back() - ys.front();
		for(size_t i = 0;i+1 < xs.size();i++){
			auto &[X, idx, delta] = xs[i];
			auto &[l, d, r, u] = rectangles[idx];
			seg.apply(d, u, delta);

			auto [mn, cnt] = seg.all_fold();

			U dy = total - (mn == 0 ? cnt : 0);
			U dx = std::get<0>(xs[i+1]) - X;

			ret += dy*dx;
		}

		return ret;
	}
};
#line 5 "verify/yosupo/area_of_union_of_rectangles.test.cpp"

void mmrz::solve(){
	int n;
	cin >> n;
	vector<tuple<int, int, int, int>> rectangles(n);
	for(auto &[l, d, r, u] : rectangles)cin >> l >> d >> r >> u;

	cout << area_of_union_rectangles<int>(rectangles).solve<ll>() << '\n';
}

Back to top page