백준 3392 화성 지도 (c++) : 피너클

3392번: 화성 지도

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

 

세그먼트 트리랑 스위핑으로 풀었다.

x축을 기준으로 정렬해서 왼쪽부터 오른쪽으로 스위핑할것이며

세그먼트트리고 현재 활성화되어있는 y축의 길이를 한번에 구할것이다.

 

int n;
vector<tuple<int, int, int, int>> v;
long long segtree[4 * 30000];
long long cnt[4 * 30000];

사용할 변수들이다.

v로 입력을 받고 {x축, y1축, y2축, 시작인지 종료인지} 이렇게 입력받는다.

segtree에는 범위 안에 활성화된 y축의 길이가 들어가고

cnt에는 해당 범위가 활성화 되었는지가 들어간다. 0보다 크면 활성화 된거다.

 

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		v.push_back(make_tuple(a, b, d, 0));
		v.push_back(make_tuple(c, b, d, 1));
		
	}
	sort(v.begin(), v.end());

main에서 입력받고 정렬해준다.

시작 부분에는 0을 넣고 종료 부분에는 1을 넣는다.

 

	long long ans = 0;

	int lastX;
	int nowX = get<0>(v[0]);
	int y1 = get<1>(v[0]);
	int y2 = get<2>(v[0]);
	int type = get<3>(v[0]);

	update(1, 0, 30000, y1, y2, type);

이후에 사용할 변수들이다.

ans에는 정답이 들어간다.

lastX는 현재 이전의 x좌표이다.

nowX는 현재 x좌표이다.

y1과 y2는 현재의 y좌표이고

type은 시작인지 종료인지이다.

그 후 update를 해준다.

void update(int node, int start, int end, int left, int right, int val) {
	if (end <= left || right <= start) return;
	
	if (left <= start && end <= right) {
		if (val == 0) cnt[node] += 1;
		else cnt[node] -= 1;

		if (cnt[node] > 0) segtree[node] = end - start;
		else if (start + 1 == end) segtree[node] = 0;
		else segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];

		return;
	}

	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, val);
	update(node * 2 + 1, mid, end, left, right, val);

	if (cnt[node] > 0) segtree[node] = end - start;
	else if (start + 1 == end) segtree[node] = 0;
	else segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];

	return;
}

기존의 세그먼트트리랑은 약간 다르다.

가장 큰 차이점은 기존의 세그먼트트리는 (start, mid), (mid +1, end) 이렇게 나뉘었지만 

여기서는 (start, mid), (mid, end) 이렇게 나뉜다.

	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, val);
	update(node * 2 + 1, mid, end, left, right, val);

생각해보면 간단하다.

(1, 5), (6, 10) 이렇게 나뉘면 어떻게 될까? 5~6 사이의 1칸이 사라져버린다. 그러니

(1, 5), (5, 10) 이렇게 나누는 것이다.

void update(int node, int start, int end, int left, int right, int val) {
	if (end <= left || right <= start) return;

범위 밖이면 바로 종료하고

	if (left <= start && end <= right) {
		if (val == 0) cnt[node] += 1;
		else cnt[node] -= 1;

범위 안일때

val이 0이라면, type이 0이라면, 시작이라면 cnt에 +1을 해주고 아니면 -1을 해준다.

		if (cnt[node] > 0) segtree[node] = end - start;
		else if (start + 1 == end) segtree[node] = 0;
		else segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];

		return;
	}

그 후 cnt가 0보다 크면 end-start 모두다 활성화 되었다는 의미니 end-start를 넣어주고

cnt가 0인 상황에서

start + 1 == end라면 0을 넣어준다. 

start == end일때가 아닌 start + 1 == end일때이다. 

(5, 6) 여기 사이에 활성화된 y가 없다면 당연히 0이다. (5, 5) 이건 고려대상이 아니다.

start + 1 != end라면 양측 자식들의 값의 합으로 해준다.

	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, val);
	update(node * 2 + 1, mid, end, left, right, val);

	if (cnt[node] > 0) segtree[node] = end - start;
	else if (start + 1 == end) segtree[node] = 0;
	else segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];

	return;
}

만약 start와 end가 범위안에 들어있지 않다면

자식들을 udpate해준뒤

똑같이 진행해주면 된다.

	for (int i = 1; i < v.size(); i++) {
		lastX = get<0>(v[i - 1]);

		nowX = get<0>(v[i]);
		y1 = get<1>(v[i]);
		y2 = get<2>(v[i]);
		type = get<3>(v[i]);

		//cout << y1 << ' ' << y2 << '\n';

		ans += (nowX - lastX) * segtree[1];
		//cout << segtree[1] << '\n';

		update(1, 0, 30000, y1, y2, type);
	}

	cout << ans << '\n';


	return 0;

}

update는 끝이고 이젠 main에서이다. for문을 1부터 시작한다. 0은 위에서 미리 처리했다.

필요한 변수들 전부 꺼내주고

ans에 (현재 x좌표 - 이전 x좌표) * (활성화된 y의 길이) 를 곱해준다.

그 후 update해주면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;

int n;
vector<tuple<int, int, int, int>> v;
long long segtree[4 * 30000];
long long cnt[4 * 30000];

void update(int node, int start, int end, int left, int right, int val) {
	if (end <= left || right <= start) return;
	
	if (left <= start && end <= right) {
		if (val == 0) cnt[node] += 1;
		else cnt[node] -= 1;

		if (cnt[node] > 0) segtree[node] = end - start;
		else if (start + 1 == end) segtree[node] = 0;
		else segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];

		return;
	}

	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, val);
	update(node * 2 + 1, mid, end, left, right, val);

	if (cnt[node] > 0) segtree[node] = end - start;
	else if (start + 1 == end) segtree[node] = 0;
	else segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];

	return;
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		v.push_back(make_tuple(a, b, d, 0));
		v.push_back(make_tuple(c, b, d, 1));
		
	}
	sort(v.begin(), v.end());

	long long ans = 0;

	int lastX;
	int nowX = get<0>(v[0]);
	int y1 = get<1>(v[0]);
	int y2 = get<2>(v[0]);
	int type = get<3>(v[0]);

	update(1, 0, 30000, y1, y2, type);

	for (int i = 1; i < v.size(); i++) {
		lastX = get<0>(v[i - 1]);

		nowX = get<0>(v[i]);
		y1 = get<1>(v[i]);
		y2 = get<2>(v[i]);
		type = get<3>(v[i]);

		ans += (nowX - lastX) * segtree[1];

		update(1, 0, 30000, y1, y2, type);
	}

	cout << ans << '\n';


	return 0;

}

전체코드다.