글 읽기 - 7626번 질문 있습니다.

companyofpotato 3년 전 1

3392번 "화성 지도"는 세그먼트 트리와 스위핑으로 맞추고, 이 문제에 도전하는 중입니다. x, y좌표가 10^9까지 들어오기 때문에, 좌표를 직접 다루는 세그먼트 트리를 만들지는 않았습니다. 대신 y좌표를 크기순으로 정렬해서 해시 테이블을 만들고 그 값을 세그먼트 트리에 저장하는 식으로 구현했습니다. 그리고 y축에 평행한 축으로 x값을 증가시키면서 스위핑하는 방식을 사용했는데, 사각형의 세로변을 만날 때마다 y값 갱신 부분을 어떻게 처리해야 할 지 모르겠습니다.

예를 들어 0, 1, 2를 갱신하고자 할 때, 0과 1은 같은 범위로 묶어서 처리가능한데 2만 따로 밖으로 나와버리니 1과 2 사이의 y값들을 처리할 방법을 모르겠습니다.

사용한 반례는

2
10 20 10 20
15 25 15 30

입니다.(정답은 225)

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define N 400000

using namespace std;

//세로변을 나타내는 클래스
class line
{
public:
	int tx, ty1, ty2, tdef;//사각형이 시작하는 세로변인지, 끝나는 세로변인지 tdef값으로 구분한다.
	line(int x, int y1, int y2, int def)
	{
		tx = x; ty1 = y1; ty2 = y2; tdef = def;
	}

	bool operator <(line& tline)
	{
		if (this->tx == tline.tx)
		{
			return this->tdef < tline.tdef;
		}
		return this->tx < tline.tx;
	}
};

int* tree, * cnt;
map<int, int> zy; //y좌표가 몇 번째로 큰 값인지 저장해서 해시테이블 형성
set<int> ys;
vector<int> yz; //i번째 값은 i번째로 큰 y좌표이다.

//세그먼트 트리에 값을 갱신하는 함수
void update(int st, int end, int cur, int left, int right, int dif)
{
	if (st > right || end < left)
		return;
	if (left <= st && end <= right)
	{
		cnt[cur] += dif;
	}
	else
	{
		int mid = (st + end) / 2;
		update(st, mid, cur * 2, left, right, dif);
		update(mid + 1, end, cur * 2 + 1, left, right, dif);
	}

	//cnt 값이 0보다 크다면, 해당 구간이 넓이에 포함된다.
	if (cnt[cur])
	{
		tree[cur] = yz[end] - yz[st];
	}
	else
	{
		if (st == end)
			tree[cur] = 0;
		else
			tree[cur] = tree[cur * 2] + tree[cur * 2 + 1];
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, x1, x2, y1, y2;
	long long ans = 0;

	tree = new int[N * 4];
	fill_n(tree, N * 4, 0);
	cnt = new int[N * 4];
	fill_n(cnt, N * 4, 0);

	cin >> n;

	vector<line> v;
	for (int i = 0; i < n; i++)
	{
		cin >> x1 >> x2 >> y1 >> y2;
		ys.insert(y1); ys.insert(y2);
		v.push_back(line(x1, y1, y2, 1));
		v.push_back(line(x2, y1, y2, -1));
	}

	sort(v.begin(), v.end());

	for (auto i : ys)
	{
		yz.push_back(i);
		zy[i] = yz.end() - yz.begin() - 1;
	}

	for (int i = 0; i < n * 2; i++)
	{
		if (i > 0)
		{
			ans += (long long)tree[1] * ((long long)v[i].tx - v[i - 1].tx);
		}
		update(0, N - 1, 1, zy[v[i].ty1], zy[v[i].ty2], v[i].tdef);
	}

	cout << ans;

	return 0;
}

powerlsj7 11달 전 0

덕분에 풀었습니다. 사용하신 반례가 도움이 되었습니다!!

2
10 20 10 20
15 25 15 30

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

7626번 질문 있습니다.

companyofpotato 3년 전 1

powerlsj7 11달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말