[백준] 3392: 화성지도

0. 문제 주소

 

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

3392번: 화성 지도

 

 

1. 풀이

 

스위핑 풀이는 쉽게 이해가 갔다.

 

 

문제는 지금까지 유효한 y 좌표를, 즉 0번 이상 덮여져 있는 y 좌표가 얼마나 있는지를 알아야 하는데

 

update도 구간으로 주어져서 처음에는 lazy propagation을 생각했었다.

 

이 경우 lazy 배열을 이용한 느린 전파 ~ 0보다 큰 좌표의 개수의 합 연산 사이에서 구현이 어려워졌다.

 

그래서 구글링을 해보니까 기존과 동일한 세그먼트 트리를 쓰되 cnt 배열을 새로 만들고 다음과 같이 정의하는 방식이 있었다.

 

cnt[node] = 이 노드가 나타내는 구간 전부에 가해졌던 변화량을 누적하여 저장

 

 

예시를 통해 이해해보면,

 

 

3번 좌표부터 7번 좌표까지 1을 추가한다고 가정해 보자.

 

여러 단계를 거쳐 left = 0, right = 7을 나타내는 node가 호출되었을 것이다.

 

구간에 완전히 포함되지 않으므로 [0, 3] 구간과 [4, 7] 구간으로 나누어 호출된다.

 

여기서 [4, 7] 구간은 추가하려고 하는 구간에 완전히 포함되므로, cnt 배열에 1을 추가할 수 있다.

 

다시 말해 cnt[ "[4,7]을 나타내는 node" ] += 1이 되고, 이는 [4, 7] 구간에 전부 1을 더했다는 말과 같다.

 

 

이걸 이용해서 뭘 할 수 있냐면,

 

만약 세그먼트 트리의 어떤 node에 대해서 cnt[node]가 0보다 클 경우, 이 node가 나타내는 구간 전부는

 

0보다 크다는 뜻과 같다. lazy propagation의 lazy 배열, propagate 함수와 매우 유사하다.

 

 

유의할 점은 연산을 하려는 구간에 완전히 포함되었다고 해서 cnt 배열에 변화량만 더해주고 함수를 끝내서는 안된다는 부분인데,

 

당연하게도 우리는 아직 cnt 배열만 갱신했을 뿐 세그먼트 트리의 노드는 갱신하지 않았기 때문이다.

 

tree[node]가 "node가 나타내는 구간에 존재하는 0보다 큰 값들의 개수"으로 저장되길 원함을 기억하자.

 

 

이 부분은 앞서 구간에 대한 처리와 cnt 배열에 대한 갱신이 끝난 뒤,

 

만약 이번 노드가 갖는 cnt 값이 0보다 커질 경우, 세그먼트 트리의 노드에 구간의 크기를 저장해두면 된다.

(구간 전부가 0보다 크다는 뜻이므로)

 

아닐 경우, 만약 leaf 노드라면 0으로 설정을 해주고, 아닐 경우 양쪽 자식 노드들의 합으로 트리를 갱신해 주면 된다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>

const int MAX = 30005;
using namespace std;

struct edge{
	int x, y1, y2;
	bool is_start;
	edge(int a, int b, int c, bool d){
		x = a;
		y1 = b;
		y2 = c;
		is_start = d;
	}
	bool operator < (const edge &b) const {
		return x < b.x;
	}
};

int N, leaf_size;
vector<edge> E;
int tree[4*MAX];
int cnt[4*MAX];
// cnt[i] : positive if every child of node i is positive

void update(int node, int l, int r, int s, int e, int diff){
	if (r < s || e < l) return;
	if (s <= l && r <= e) cnt[node] += diff;
	else{
		int mid = (l+r) / 2;
		update(node*2, l, mid, s, e, diff);
		update(node*2+1, mid+1, r, s, e, diff);
	}
	if (cnt[node] > 0) tree[node] = r-l+1;
	else {
		if (l == r) tree[node] = 0;
		else tree[node] = tree[node*2] + tree[node*2+1];
	}
	
}


int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	#endif

	// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	scanf("%d", &N);
	leaf_size = 1 << ((int)ceil(log2(MAX)));
	for (int i=0;i<N;i++){
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		E.push_back({x1, y1, y2-1, true});
		E.push_back({x2, y1, y2-1, false});
	}
	sort(E.begin(), E.end());
	int ans = 0;
	auto pre = E[0];
	update(1, 0, leaf_size-1, pre.y1, pre.y2, 1);
	for (int i=1;i<2*N;i++){
		auto curr = E[i];
		int dx = curr.x - pre.x;
		int cnt = tree[1];
		ans += dx * cnt;
		if (curr.is_start) update(1, 0, leaf_size-1, curr.y1, curr.y2, 1);
		else update(1, 0, leaf_size-1, curr.y1, curr.y2, -1);
		pre = curr;
	}
	printf("%d\n", ans);
		
	
	return 0;
}