BOJ 3392 - 화성지도 (세그트리 응용)

https://www.acmicpc.net/problem/3392

코드는 다음 블로그의 코드를 많이 참조했습니다.

https://jason9319.tistory.com/58

 

일반적인 세그트리의 형태를 따르지 않고, 세그먼트트리의 구조를 이용하여 풀 수 있는 문제.

 

<문제설명>

좌표가 최대 30000인 2차원 평면 상에 최대 1e4개의 직사각형이 주어질 때, 직사각형들이 이루는 영역의 크기를 구하라

 

 

<풀이>

x좌표가 증가하는 순서대로 막대기들을 볼 때, "이전 x좌표와의 차 dx"와 "y좌표들의 psum이 1이상인 곳의 개수"를 곱해나가면 된다.

 

지금 막대기가 [y1,y2)일 떄 이 막대기가 시작 막대기인 경우 해당구간을 모두 +1, 끝 막대기인 경우 해당구간을 모두 -1해주며 배열을 유지해 나간다고 생각해야 한다.

 

이걸 lazy propagation을 사용해서 구현하려고 하면 다소 복잡하다. 실제로 할 수 있는지도 모르겠다.

 

세그먼트트리의 구조를 이용해서, 업데이트할 구간에 [ns,ne]가 들어가면, 그 구간 안의 모든 요소들을 update해야한다는 의미이다. 이것을 세그먼트트리의 second에 유지해두둔다. 업데이트할 구간에 [ns,ne]가 들어가지 않는다면 왼쪽,오른쪽 자식노드에 대해서 계속 업데이트를 해 나간다.

 

재귀의 맨 끝에 도달하여 반환하기 시작하면서 second값과 왼쪽,오른쪽 자식노드의 first(실제 값)을 기반으로 현재 노드의 first(실제 값)을 갱신해 나가면 된다.

 

현재 노드의 second값이 1이상이라면 그 구간에 포함되는 모든 요소들의 개수를 first 값으로 취한다.

현재 노드의 second값이 0이하라면 왼쪽,오른쪽 자식노드의 first값을 더해준다.

 

 

<코드>

const int MAX = 2e4 + 4;
const int SMAX = (1 << 18);

ll n,px;
vector<T> a;
P seg[SMAX];

void update(int s, int e, int x, int i = 1, int ns = 0, int ne = SMAX / 2 - 1) {
	if (e < ns || ne < s) return;
	if (s <= ns && ne <= e) {
		seg[i].second += x;
	}
	else {
		int md = (ns + ne) / 2;
		update(s, e, x, i * 2, ns, md);
		update(s, e, x, i * 2 + 1, md + 1, ne);
	}

	if (seg[i].second > 0) seg[i].first = ne - ns + 1;
	else {
		if (ns == ne) seg[i].first = 0;
		else seg[i].first = seg[i * 2].first + seg[i * 2 + 1].first;
	}
}

int main() {
	FAST; cin >> n;
	for (int i = 0,x1,y1,x2,y2; i < n; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		a.push_back({ x1,y1,y2 - y1 });
		a.push_back({ -x2,y1,y2 - y1 });
	}
	sort(a.begin(), a.end(), [](T t1, T t2) {
		return abs(get<0>(t1)) < abs(get<0>(t2));
		});

	ll ans = 0;
	for (ll i = 0,x,y,d; i < a.size(); i++) {
		tie(x, y, d) = a[i];
		ans += seg[1].first * (abs(x)-px);
		
		update(y, y + d-1, (x >= 0 ? 1 : -1));
		px = abs(x);
	}
	cout << ans << '\n';
}