Boj 7626) 직사각형

문제

백준 7626

설명

화성지도 문제의 버전업이다.

이 문제를 풀기위해 Plain Sweeping, Segment Tree, Coordinate Compression 기법을 사용해야한다.

Plain Sweeping

Plain Sweeping 골자 코드

using ii = pair<int, int>;
int masks[MAX_IN];
vector<ii> Begins[MAX_IN], Ends[MAX_IN];

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		Begins[y1].push_back({ x1, x2 }); // y1 지점에서 사각형이 시작한다.
		Ends[y2].push_back({ x1, x2 });   // y2 지점에서 사각형이 끝난다.
	}

	long long ans = 0;

	// X 축에 대해서 스위핑을 진행한다.
	for (int i = 0; i < MAX_IN; i++)
	{
		// 먼저 삽입/삭제를 진행한다.
		for (auto& b : Begins[i])
			for (int j = b.first; j < b.second; j++)
				masks[j]++;
		for (auto& b : Ends[i])
			for (int j = b.first; j < b.second; j++)
				masks[j]--;

		// masked height 를 구한다.
		int height = 0;
		for (int j = 0; j < MAX_IN; j++)
			if (masks[j]) height++;

		// 1칸씩 움직이므로 1 * height 를 더해 넓이를 추가한다.
		ans += height;
	}
	cout << ans;
}

기본적인 전략을 위 코드가 나타내고 있다. SISOBUS Blog 에 있는 그림을 참고해보자.

X 축 좌표압축

Plain Sweeping 골자 코드

using ii = pair<int, int>;
int masks[MAX_IN];

struct RECT {
	int x, v, t, b;
	bool operator < (const RECT& in) const {
		return x != in.x ? x < in.x : v > in.v;
	}
};
vector<RECT> rects;

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		rects.push_back({ x1, +1, y1, y2 });
		rects.push_back({ x2, -1, y1, y2 });
	}
	sort(rects.begin(), rects.end());

	long long ans = 0;

	int prev_x, cur_x = 0;
	for (int i = 0; i < rects.size(); i++)
	{
		prev_x = cur_x;
		cur_x = rects[i].x;

		int height = 0;
		for (int j = 0; j < MAX_IN; j++)
			if (masks[j]) height++;
		ans += (cur_x - prev_x) * height;
		
		for (int j = rects[i].t; j < rects[i].b; j++)
			masks[j] += rects[i].v;
	}
	cout << ans;
}

Plainng Sweeping 은 Sweeping 되는 한 축을 따라 가면서 삽입/삭제 연산을 수행하게 된다. 연산이 수행되는 위치와 연산에 관련된 정보 그리고 삽입/삭제인지 나타내는 값을 자료구조로 만들어 좌표압축을 수행하면 모든 범위에 대해 체크를 하지 않아도 되게 된다.

삽입 삭제 최적화

특정 범위의 Mask 값을 하나하나 체크하고 증감시키면 너무 느리다. 이를 위한 자료구조가 Lazy Segment Tree 이다. 세그먼트 트리의 중간노드가 수정해야 할 범위에 포함된다면 굳이 자식노드까지 가지 않음으로써, Leaf Node 까지 탐색하는 횟수가 많아봐야 범위 양쪽에서 수행되는 2번으로 그치게 된다. 그래서 시간복잡도가 선형이 아닌 로그가 되는 것이다.

보통 이런 Lazy Segment Tree 는 Propagation 연산을 수행하지만 여기선 그렇지 않다. 왜냐하면 우리는 Mask 값이 1 이상인 범위를 구해야하기 때문이다. 만약 Propagation 을 수행한다면 중간노드의 Mask 값만으로 자식노드들이 모두 Mask 되어 있는지 알 수 없어진다. 일부 자식 노드에서만 Mask 값이 몰려있는지, 자식 노드들에 고르게 Mask 값이 들어있는지 알 도리가 없기 때문이다.

대신 중간 노드에서 Mask 를 수정만 한다면 자식 노드에 대한 정보는 바로 알 수 있다. Mask 값이 1 이상이면 자식노드들은 모두 Mask 가 1 이상이다. 만약 0 이면 자식노드에서의 범위를 가져오면 된다. 이를 재귀적으로 수행하면 로그시간단위로 Mask 값을 수정하고 및 범위의 크기를 알 수 있다.

Y 축 좌표압축

이 문제는 Y 축 범위가 매우 크므로 역시 좌표압축을 해주어야한다. 그런데 세그먼트 트리에서의 좌표압축은 꽤나 헷갈리는 부분이 많다.

위 세그먼트 트리의 구현은 [s, e) 가 아닌 [s, e] 범위에 대해 수행된다. 좌표압축 전에는 Leaf Node 가 균등하게 길이 1을 나타냈으므로 [s, e] 가 나타내는 길이는 e - s + 1 이 된다. 하지만 좌표압축이 되면 균등함이 보장되지 않아 이렇게 계산할 수 없다.

대신 ys[e] - ys[s-1] 이거나 ys[e+1] - ys[s] 중 하나로 계산할 수 있을 것이다. 편의상 범위가 [left, right] 로 들어왔을 때 left 미만으로 값이 빠지지 않도록 ys[e+1] - ys[s] 로 계산하자.

그러면 문제가 생기는 것이 범위의 끝부분에서 초과가 된다는 것이다. 예를들어 ys[r+1] - ys[r] 이렇게 말이다. 그래서 업데이트 시에 right 에서 하나를 빼줘서 사용해야한다.

또한 위 세그먼트 트리는 인덱스를 1 부터 시작하므로 기본적으로 오프셋을 1 을 줘야한다.

이를 고려해서 아래의 풀이코드와 같은 모양이 나온다.

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드

using ll = long long;
struct RECT {
	int x, v, t, b;
	bool operator < (const RECT& in) const {
		return x != in.x ? x < in.x : v > in.v;
	}
};
vector<RECT> rects;
vector<int> ys;

template<typename T, size_t _H>
class SegmentTree
{
	struct Node { T v = 0; int v2 = 0; };
public:
	void Update(int l, int r, T v) { assert(r <= INDEX_MAX); _t1 = l; _t2 = r; _t3 = v; Update_Recursive(1, 1, INDEX_MAX); }

private:
	void Update_Recursive(int x, int s, int e)
	{
		if (_t1 <= s && e <= _t2)  // 현재 범위가 업데이트할 범위 내에 있는 경우
			nodes[x].v2 += _t3;
		else if (!(_t2 < s || e < _t1)) {  // 현재 범위가 업데이트할 범위에 걸치는 경우
			int m = (s + e) / 2;
			Update_Recursive(2 * x, s, m);
			Update_Recursive(2 * x + 1, m + 1, e);
		}

		if (nodes[x].v2 > 0) nodes[x].v = ys[e] - ys[s-1];  // 세그먼트트리의 범위화로 [e+1, s] 에서 array start offset 1 을 빼준 결과
		else if (s != e) nodes[x].v = nodes[2 * x].v + nodes[2 * x + 1].v;
		else nodes[x].v = 0;
	}

public:
	Node nodes[1 << _H];
	int INDEX_MAX = 1 << _H - 1;
	int _t1, _t2; T _t3;
};
SegmentTree<ll, 20> seg;

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x1, y1, x2, y2;		
		cin >> x1 >> x2 >> y1 >> y2;
		rects.push_back({ x1, +1, y1, y2 });
		rects.push_back({ x2, -1, y1, y2 });
		ys.push_back(y1);
		ys.push_back(y2);
	}
    
	sort(rects.begin(), rects.end());
	sort(ys.begin(), ys.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());

	ll ans = 0;

	int prev_x = 0, cur_x = 0;
	for (auto& r : rects)
	{
		prev_x = cur_x; cur_x = r.x;
		ans += (cur_x - prev_x) * seg.nodes[1].v;
		int t = lower_bound(ys.begin(), ys.end(), r.t) - ys.begin();
		int b = lower_bound(ys.begin(), ys.end(), r.b) - ys.begin();
		seg.Update(t+1, b, r.v);  // 세그먼트 트리는 1부터 세므로 1을 더하되 범위화 때문에 끝부분은 1을 다시 제한다.
	}
	cout << ans;
}