[C++] 북서풍 (백준 5419번) - 스위핑 + 세그먼트 트리

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

 

스위핑 아이디어

우리가 하고 싶은 것: 각 섬마다 자신보다 북서쪽에 있는 섬들이 몇 개인지 -> 그것들의 합을 구하면 정답

그러므로 섬들을 x 기준 오름차순, y 기준 내림차순으로 정렬해두자.

그렇게 정렬해둔 다음에, 앞에서부터 보면서 각 섬 기준 북서쪽에 있는 섬들이 몇 개인지 셀 때 지금까지 본 섬 중 자기보다 y값이 크거나 같은 섬이 몇 개였는지만 세면 된다.

자기 기준으로 북서쪽 섬이 몇 개인지 확인 후, 자기 섬도 등록해야 한다.

 

세그먼트 트리 아이디어

지금까지 본 섬들 중 자기보다 y값이 크거나 같은 섬이 몇 개인지를 빠르게 구하기 위해서 세그먼트 트리를 사용해야 한다.

-> 세그먼트 트리에 저장해야 하는 값: 지금까지 본 섬들의 y값 분포

즉, 자기 기준으로 북서쪽 섬이 몇 개인지는 구간 합 쿼리로, 자기 섬 등록은 업데이트로 처리하면 된다.

 

p.s. 좌표 압축

좌표 범위가 크기 때문에 좌표 압축을 해주어야 한다.

y값들에 대해서만 좌표 압축을 해주면 된다.

 

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

int ysz;

struct SegTree {
    vector<long long> tree;

    long long update(int idx, int l, int r, int target, long long val) {
        if (target < l || target > r) return tree[idx];
        if (l == r) return tree[idx] = tree[idx] + val;
        int m = (l + r) / 2;
        return tree[idx] = update(idx * 2, l, m, target, val) + update(idx * 2 + 1, m + 1, r, target, val);
    }
    
    long long query(int idx, int l, int r, int wl, int wr) {
        if (wr < l || wl > r) return 0;
        if (wl <= l && wr >= r) return tree[idx];
        int m = (l + r) / 2;
        return query(idx * 2, l, m, wl, wr) + query(idx * 2 + 1, m + 1, r, wl, wr);
    }
    
    long long update(int target, long long val) {
        return update(1, 0, ysz, target, val);
    }
    
    long long query(int wl, int wr) {
        return query(1, 0, ysz, wl, wr);
    }
};

// x 기준 오름차순, x 같으면 y 기준 내림차순
bool compare(pair<int,int> &a, const pair<int,int> &b) {
    if (a.first == b.first) return a.second > b.second;
    else return a.first < b.first;
}

void solve() {
    int n;
    cin >> n;
    
    vector<pair<int, int>> p(n);
    vector<int> ycom;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        p[i] = {x, y};
        ycom.push_back(y);
    }

    sort(p.begin(), p.end(), compare);
    sort(ycom.begin(), ycom.end());
    ycom.erase(unique(ycom.begin(), ycom.end()), ycom.end());
    
    ysz = ycom.size() + 1;

    SegTree seg; // 지금까지 본 섬들의 y값 별 개수를 저장하는 세그먼트 트리
    seg.tree.assign(4 * ysz + 1, 0);

    long long ans = 0;
    for (auto [x, y]: p) {
        int yidx = lower_bound(ycom.begin(), ycom.end(), y) - ycom.begin();
        ans += seg.query(yidx, ysz);
        seg.update(yidx, 1);
    }

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)