[BOJ 5419] 북서풍(c++)

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

문제 개요

강한 북서풍이 불고 있을 때, 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있습니다. 즉, 섬 A에서 섬 B로 항해 가능한 조건은 B가 A보다 x좌표가 크거나 같고, y좌표가 작거나 같은 경우입니다. 여러 개의 섬이 좌표 평면 상에 주어졌을 때, 북서풍을 타고 항해할 수 있는 섬의 쌍의 개수를 구하는 문제입니다.

• (1 ≤ n ≤ 75,000)
• (-10⁹ ≤ xi, yi ≤ 10⁹)

---

문제 풀이

이 문제는 좌표 압축과 세그먼트 트리를 활용하여 해결하였습니다.

핵심 아이디어는 다음과 같습니다.

1. 좌표 압축: x좌표의 범위가 -10⁹ ~ 10⁹로 매우 크기 때문에, x좌표를 0부터 시작하는 인덱스로 압축합니다.
2. 정렬 전략: 섬들을 y좌표 기준으로 오름차순 정렬하되, y좌표가 같은 경우 x좌표가 큰 순서대로 정렬합니다. 이는 동일한 y좌표를 가진 섬들 간에는 항해가 불가능하므로, x좌표가 큰 섬부터 처리하여 중복 카운트를 방지하기 위함입니다.
3. 세그먼트 트리를 이용한 카운팅: y좌표가 작은 섬부터 순회하면서, 현재 섬보다 x좌표가 크거나 같은 섬들의 개수를 세그먼트 트리의 구간 쿼리로 구합니다. 이는 현재 섬에서 출발하여 도달할 수 있는 섬의 개수를 의미합니다.
4. 세그먼트 트리 업데이트: 각 섬을 처리한 후, 해당 섬의 압축된 x좌표 위치에 1을 더하여 다음 섬들이 이 섬을 도달 가능한 섬으로 카운트할 수 있도록 합니다.

y좌표가 작은 섬부터 처리하므로, 현재 섬보다 y좌표가 작거나 같으면서 x좌표가 크거나 같은 섬들을 효율적으로 찾을 수 있습니다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int mn = -2e9;

int n;
long long res;

class node {
public:
	int x, y;
};

vector<node> v;
int seg[75001 * 4];

void init() {
	v.clear();
	memset(seg, 0, sizeof(seg));
	res = 0;
	cin >> n;
	v.reserve(n);
}

int update(int x, int s, int e, int idx) {
	if (idx < s || e < idx) return seg[x];
	if (s == e) {
		return seg[x] += 1;
	}
	int mid = s + (e - s) / 2;
	return seg[x] = update(x * 2, s, mid, idx) + update(x * 2 + 1, mid + 1, e, idx);
}

int query(int x, int s, int e, int l, int r) {
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) return seg[x];
	int mid = s + (e - s) / 2;
	return query(x * 2, s, mid, l, r) + query(x * 2 + 1, mid + 1, e, l, r);
}

bool cmp_x(node a, node b) {
	return a.x < b.x;
}

bool cmp_y(node a, node b) {
	if (a.y == b.y) {
		return a.x > b.x;
	}
	return a.y < b.y;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		init();
		int x, y;
		for (int i = 0; i < n; i++) {			
			cin >> x >> y;
			v.push_back({ x, y });
		}
		sort(v.begin(), v.end(), cmp_x);
		int x_tmp = mn;
		int compress_x = -1;
		for (int i = 0; i < n; i++) {
			if(x_tmp < v[i].x) {
				x_tmp = v[i].x;
				compress_x++;
			}
			v[i].x = compress_x;
		}
		int m = compress_x;
		sort(v.begin(), v.end(), cmp_y);
		for (auto cur : v) {
			res += query(1, 0, m, cur.x, m);
			update(1, 0, m, cur.x);
		}
		cout << res << '\n';
	}
	return 0;
}