좌표압축 기법

좌표압축 기법은 Problem Solving을 하다보면 정말 정말 정말 자주 쓰이는 테크닉이다.

세그트리(or BIT) 등등.. 구간 쿼리와 함께 같이 쓰이는 경우도 많고, 오프라인 쿼리등을 처리할 때 등등 많은 경우에서 유용하게 이용된다.

개념에 대한 설명을 하기 위하여 한 문제를 예시로 들어보겠다.

N(<=100000)개의 점이 1차원 직선상에 존재한다고 가정하자. 

이때 쿼리를 M(<=100000)개 처리해야 한다. 쿼리는 x~y 구간에 있는 점의 수를 출력하는 쿼리라고 해보자.

점의 범위가 1~10만이라면 세그먼트 트리나 BIT등을 이용하여 매 쿼리를 log시간에 처리할 수 있을 것이다.

하지만 N개의 점과 x,y의 범위가 (-10억~10억) 이라고 가정해보자.

20억의 구간에 업데이트 하는건 아마 불가능하다고 생각된다. 그렇다면 어떻게 해야할까?

이럴때 사용가능한 테크닉이 좌표압축이다.

이 문제에 등장할 수 있는 좌표의 범위는 -10억~10억이지만 이 문제에 등장하는 좌표의 수는 많아봐야 N+2*M개다.

따라서 우리는 최대 N+2*M개의 좌표를 인덱싱하여 정렬 된 순서대로 1~N+2*M의 번호를 매겨준 뒤 BIT등을 이용하여 답을 구해낼 수 있다.

for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    idx.push_back(a[i]);
}
for (int i=  0; i < m; i++) {
    scanf("%d%d",qry[i].first, qry[i].second);
    idx.push_back(qry[i].first);
    idx.push_back(qry[i].second);
}
sort(idx.begin(), idx.end());
idx.erase(unique(idx.begin(), idx.end()), idx.end());

 

이런식으로 등장하는 모든 좌표를 idx라는 벡터에 넣어준 뒤 정렬해준 후 중복되는 값들을 지워주고 나면

int getidx(int x){
    return lower_bound(idx.begin(), idx.end(), x) - idx.begin();
}

이러한 간단한 함수를 선언해주면 해당값에 대한 인덱스를 편하게 받아올 수 있다.

이러한 인덱스가 정렬 된 순서라는 걸 이용하면 구간에 대한 쿼리를 아름답게 처리해 줄 수 있다.