[백준] 5419 북서풍

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. → 조건1. 내가 갈 수 있는 섬의 x좌표는 나보다 크거나 같다. 조건2. 조건1을 만족할 때, 내가 갈 수 있는 섬의 y좌표는 나보다 작거나 같다. ==>  (입력받을 때 y에 -1를 곱한다면) 조건1. 내가 갈 수 있는 섬의 x좌표는 나보다 크거나 같다. 조건2. 조건1을 만족할 때, 내가 갈 수 있는 섬의 y좌표는 나보다 크거나 같다.

x, y 좌표를 오름차순으로 정렬했을 때, 하나씩 탐색하면 x 조건은 자동으로 성립한다. → 따라서 정렬하면 x 좌표값이 필요없게 됨. y 좌표만 보고 y 조건이 성립하는지 판단하는 문제로 변함. 하나씩 탐색을 했을 때 해당 y 좌표보다 작은 섬들이 기존에 몇 개 존재하는지 확인하면 됨 → 누적합, 세그먼트 트리로 구현 가능.

 

각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 xi, yi가 주어진다. 두 섬의 좌표가 같은 경우는 없다. (-10^9 ≤ xi, yi ≤ 10^9) → x, y 좌표값이 2*10^9의 범위를 가지는데, 섬의 개수는 최대 75,000개이다. 즉, 좌표의 유니크한 값이 최대 75,000개가 나올 수 있다. x, y 좌표를 사용할 필요없이 좌표값들의 크고 작은 정도를 통해 표현할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
#define MAX_N 75001

int T, n, x, y, N;
vector<pair<int, int>> island;
map<int, int> y_mapping;
ll tree[MAX_N*4], ans;

void init_() {
    island.clear();
    y_mapping.clear();
    ans = 0;
    fill(&tree[0], &tree[MAX_N*4], 0);
}

void update(int cur_node, int start, int end, int target_node) {
    if (start > target_node || end < target_node) return ;
    
    tree[cur_node] += 1;

    if (start != end) {
        update(cur_node*2, start, (start+end)/2, target_node);
        update(cur_node*2+1, (start+end)/2+1, end, target_node);
    }
}

ll search(int cur_node, int start, int end, int target_start, int target_end) {
    if (target_end < start || end < target_start) return 0;
    if (target_start <= start && end <= target_end) return tree[cur_node];
    return search(cur_node*2, start, (start+end)/2, target_start, target_end) + search(cur_node*2+1, (start+end)/2+1, end, target_start, target_end);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> T;
    while (T--) {
        init_();
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> x >> y;
            island.push_back({x, -y});
            y_mapping.insert({-y, 0});
        }
        // y 매핑
        y = 1;
        for (pair<int, int> ym : y_mapping) {
            y_mapping[ym.first] = y++;
        }
        N = y_mapping.size();
        // 정렬
        sort(island.begin(), island.end());
        // 순서대로 서치 & 업데이트
        for (pair<int, int> xy : island) {
            y = y_mapping[xy.second];
            ans += search(1, 1, N, 1, y);
            update(1, 1, N, y);
        }

        cout << ans << '\n';
    }


    return 0;
}