https://www.acmicpc.net/problem/5419
5419번: 북서풍
문제 강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. 작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에
www.acmicpc.net
세그먼트 트리와 좌표압축을 통해서 해결 할 수 있다.
우선 pair< x, y > 형태로 입력을 모두 받은뒤에
x축정렬(같다면 y가 큰것부터)을 시행한다.
X축 정렬을 하고난뒤에는
k번째 좌표에서 k번째와 짝지어질 수 있는 좌표는 (0 ~ k-1) 좌표 중에 있을 것이다.
그 좌표들 중에서 k번째보다 y값이 큰것들이 해당 좌표에서 짝 지을 수 있는 좌표들이 된다.
x의 범위는 정렬을통해 인덱스로 체크 하면 되기때문에 상관 없지만 y의 범위가
(-10e9 ≤ xi, yi ≤ 10e9)이기 때문에 세그먼트 트리의 노드에 모든 y 값을 담을 수 없다.
그래서 좌표압축을 사용한다.
y만 담겨져 있는 vector를 입력때 하나 더만들어서 y축( 내림차순 ) 으로 입력받은뒤
upper_bound를 통해서 해당 y값이 몇번째로 큰 값인지 index를 확인해서
그 index가 결국 세그먼트의 target node index가 된다.
0~index까지 구간합을 결과값에 더해주면 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 75001
int tree[MAX_N * 4];
vector<pair<int, int> > vec;
vector<int> y_vec;
void init_tree(int now, int start, int end) {
if (start > end) return;
if (start == end) {
tree[now] = 0;
return;
}
tree[now] = 0;
int mid = (start + end) / 2;
init_tree(now * 2, start, mid);
init_tree(now * 2 + 1, mid + 1, end);
}
void update_tree(int now, int target, int start, int end) {
if (target > end || target < start) return;
if (start == end) {
tree[now]++;
return;
}
int mid = (start + end) / 2;
update_tree(now * 2, target, start, mid);
update_tree(now * 2 + 1, target, mid + 1, end);
tree[now] = tree[now * 2] + tree[now * 2 + 1];
}
int query(int now, int left, int right, int start, int end) {
if (left > end || right < start) return 0;
if (left <= start && end <= right) {
return tree[now];
}
int mid = (start + end) / 2;
return (
query(now * 2, left, right, start, mid) +
query(now * 2 + 1, left, right, mid + 1, end)
);
}
bool cmp_x_y(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
bool cmp_y(int a, int b) {
return a > b;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T; cin >> T;
while (T--) {
int N; cin >> N;
vec.clear();
y_vec.clear();
init_tree(1, 0, N - 1);
for (int i = 0; i < N; i++) {
int x, y; cin >> x >> y;
vec.push_back({ x,y });
y_vec.push_back(y);
}
long long ret = 0;
sort(vec.begin(), vec.end(),cmp_x_y);
sort(y_vec.begin(), y_vec.end(), cmp_y);
for (int i = 0; i < vec.size(); i++) {
int x = vec[i].first, y = vec[i].second;
int index = upper_bound(y_vec.begin(), y_vec.end(), y, cmp_y) - y_vec.begin() - 1;
ret += query(1, 0, index, 0, N - 1);
update_tree(1, index, 0, N - 1);
}
cout << ret << "\n";
}
}