[백준 5419번] [세그먼트 트리 / 좌표 압축 / 스위핑] 북서풍

Approach

본질적으로 위 문제와 접근방법이 완전히 동일하다.

https://viyoung.tistory.com/393

[백준 2336번] [세그먼트 트리 / 스위핑] 굉장한 학생

기본적으로 특정 점에 데헤 차례차례 update하면서 세그먼트 트리에 쿼리를 날리게 되면, 2가지 기준에 대해서 동시에 처리할 수 있는 테크닉에 대해서 잘 알아두도록 하자.

 

추가적으로 이 문제는 북서풍을 타고 이동하는 것이지만, 북서풍쪽으로 이동할 수 있는 섬을 찾아도 괜찮다.

따라서, x축 기준으로 오름차순, y축 기준으로 내림차순으로 정렬한 뒤 순서대로 업데이트하면서 쿼리를 날려주면 된다. 이때의 세그트리는 구간합 세그이다.

 

즉 이렇게 되면 현재 바라보고 있는 점의 x좌표를 x_cor, y좌표를 y_cor라고 할 때, y_cor ~ inf까지 놓인 점의 위치를 판단하는 것과, 1 ~ x_cor이고 y_cor ~ inf에 놓인 점의 개수를 구하는 것과 동치가 된다. 근데, y_cor의 좌표가 -10억~ 10억이므로 그대로 메모리를 잡으면 터지므로 좌표압축을 추가적으로 진행해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
int seg[400000];
vector<int> y_compress;

void update(int node, int start, int end, int index){
    if(index < start || end < index) return;
    if(start == end){
        seg[node] += 1;
        return;
    }
    seg[node] += 1;
    int mid = (start + end) >> 1;
    update(node * 2, start, mid, index);
    update(node * 2 + 1, mid + 1, end, index);
}

int query(int node, int start, int end, int left, int right){
    if(right < start || end < left) return 0;
    if(left <= start && end <= right) return seg[node];
    int mid = (start + end) >> 1;
    return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
}

int find_y_cor(int val){
    // 시작 인덱스를 1로 잡음
    return (lower_bound(y_compress.begin(), y_compress.end(), val) - y_compress.begin()) + 1;
}

bool cmp(pii &v1, pii &v2){
    if(v1.first == v2.first){
        return v1.second > v2.second;
    }
    else return v1.first < v2.first;
}

int main() {
    fastio;
    int t;
    cin >> t;
    for(int test_num = 1; test_num <= t; ++test_num){
        memset(seg, 0, sizeof(seg));
        vector<pii> v;
        y_compress = {}; // clearing
        int n;
        cin >> n;
        for(int i = 0; i < n; i++){
            int a, b;
            cin >> a >> b;
            v.push_back({a, b});
            y_compress.push_back(b);
        }
        sort(v.begin(), v.end(), cmp);
        sort(y_compress.begin(), y_compress.end());
        y_compress.erase(unique(y_compress.begin(), y_compress.end()), y_compress.end());

        ll ret = 0;
        for(int i = 0; i < n; i++){
            int cur_y_compress = find_y_cor(v[i].second);
            ret += query(1, 1, n, cur_y_compress, n);
            update(1, 1, n, cur_y_compress);
        }
        cout << ret << "\n";
    }
    return 0;
}