BOJ)5419 북서풍

문제: icpc.me/5419

북서풍을 타고 항해할 수 있는 섬의 쌍의 개수를 구하는 문제이다.

여기서 북서풍을 타고 항해할 수 있는 섬이란 어떤 섬 기준으로 x좌표가 해당하는 섬보다 크거나 같고 y좌표가 해당하는 섬보다 작거나 같은 섬들을 말한다.

결국 우리는 각 섬마다 x좌표가 작으면서 y좌표는 큰 섬들의 개수를 구한 뒤 그 합을 출력하면 된다.

우리는 x좌표가 작은 수를 우선적으로 정렬하되 x좌표가 같을 경우 y좌표가 큰 수를 우선적으로 정렬을 할 것이다.

이렇게 정렬을 했을 시에 먼저 등장하는 좌표뒤에 나오는 좌표들 중 북서풍을 타고 항해할 수 있는 섬이 없다는 것은 자명하다.

따라서 우리는 정렬을 해준 뒤 순서대로 봐주면 된다.

x좌표 기준으로 정렬을 했으므로 우리는 먼저 등장했던 섬들 중에서 y좌표가 내가 현재 보고 있는 섬보다 큰 섬들의 개수만 세주면 된다.

이는 세그먼트 트리를 이용하여 구해줄 수 있는데 이때 좌표가 10^9까지 등장하기 때문에 좌표를 노드로 만들기에는 무리가 있다.

따라서 우리는 좌표 압축 기법을 사용하여 y좌표를 좌표 압축 해준 뒤 인덱스를 얻어 세그먼트 트리에 업데이트 시켜준 후 현재 보고 있는 섬보다 큰 y좌표의 개수를 구해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX_N 100000
using namespace std;
int t, n, x, y, seg[4 * MAX_N], b[MAX_N];
pair<int,int> a[MAX_N + 1];
bool cmp(pair<int, int> x, pair<int, int> y) {
    if (x.first == y.first)
        return x.second > y.second;
    return x.first < y.first;
}
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(seg, 0, sizeof(seg));
        memset(b, 0, sizeof(b));
        long long res = 0;
        scanf("%d", &n);
        vector<int> ypos;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x, &y);
            a[i] = { x,y };
            ypos.push_back(y);
        }
        sort(a + 1, a + n + 1, cmp);
        sort(ypos.begin(), ypos.end());
        ypos.erase(unique(ypos.begin(), ypos.end()), ypos.end());
        for (int i = 1; i <= n; i++) {
            int z = lower_bound(ypos.begin(), ypos.end(), a[i].second) - ypos.begin();
            res += (long long)query(z, n - 1, 1, 0, n - 1);
            b[z]++;
            update(z, b[z], 1, 0, n - 1);
        }
        printf("%lld\n", res);
    }
    return 0;
}