[BOJ] 5419 | 북서풍

문제

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

풀이

임의의 한 섬(a,b)을 기준으로, 그 점과 이어질 수 있는 섬(c,d)들은 모두 a<=c와 b>c를 만족해야한다.

이를 이용하여, y축을 기준으로 오름차순으로 정렬하고, y축이 같은 경우는 x기준으로 내림차순으로 정렬하면, 아무 섬이나 잡아도, 해당 섬 이전에 선택된 섬들은 모두 해당 섬보다 남쪽에 있을 것임이 자명하다. 또한 이전에 선택된 섬들 중에, 해당 섬보다 동쪽에 있는 섬들의 개수를 세주면, 해당 섬보다 남쪽에 있으면서 동쪽에 있는 섬들을 모두 선택할 수 있게 된다.

단, 좌표가 -10^9~10^9이므로, O(N)으로 가능한 X좌표들을 모두 저장해두고, 이분 탐색으로 index 위치를 찾는다.

섬들의 개수는 세그먼트 트리로 O(logN)만에 구할 수 있으며, 개수 업데이트에 O(logN), 이분 탐색에 O(logN)이므로,

모든 점 탐색은O(NlogN)만에 가능하다.

소스

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define P pair<int,int>
using namespace std;

int tree[400000], num[80000], MAX, T,N;

bool cmp1(P a, P b) { return a.first < b.first; }
bool cmp2(P a, P b) { return (a.second == b.second) ? (a.first > b.first):(a.second < b.second); }

void update(int p, int v) {
	p += MAX;
	tree[p] += v;
	for (; p /= 2; tree[p] = tree[2 * p] + tree[2 * p + 1]);
}

int sum(int s, int e) {
	int res = 0;
	s += MAX, e += MAX;
	while (s < e) {
		if (s % 2)
			res += tree[s++];
		if (e % 2 == 0)
			res += tree[e--];
		s /= 2, e /= 2;
	}
	if (e == s)
		res += tree[s];
	return res;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> T;
;	while (T--) {
		long long size = 0, res=0; 
		vector<P> V;
		cin >> N;
		for (MAX = 1; MAX < N; MAX *= 2);
		memset(tree, 0, sizeof(tree));
		memset(num, 0, sizeof(num));
		for (int i = 0; i < N; i++) {
			int x, y;
			cin >> x >> y;
			V.push_back({ x,y });
		}
		sort(V.begin(), V.end(), cmp1);
		for (int i = 0; i < V.size(); i++) {
			if (!i || num[size] != V[i].first)
				num[size++] = V[i].first;
		}
		sort(V.begin(), V.end(), cmp2);
		for (P idx : V) {
			int l = 0, r = size-1;
			while (l < r) {
				int m = (l + r) / 2;
				if (num[m] > idx.first)
					r = m - 1;
				else if (num[m] < idx.first)
					l = m + 1;
				else {
					l = m;
					break;
				}
			}
			res += sum(l, size);
			update(l, 1);
		}
		cout << res << "\n";
	}
}