[백준 2517번] [세그먼트 트리 / 좌표 압축] 달리기

Approach

문제를 잘 이해해보면, 현재 자신을 기준으로 자기보다 큰 숫자의 개수 + 1이 자기 등수이다.

이때, 큰 수부터 처리하면서 쿼리를 업데이트하면 이를 구간합으로 바꿔 이해할 수 있다.

update하면서 해당 index가 속한 쿼리에 +1씩 시켜주면 된다.

 

또한, 실력 지표의 범위에 비해서 선수가 압도적으로 적기도 하고 해당 숫자가 너무 크다. 따라서 좌표 압축을 해서 seg의 크기를 줄이도록 하자. 만약 줄이지 해당 점수의 max의 4배를 해야하는데, 당연히 메모리 초과가 난다.

 

추가적으로 자신의 위치를 처리해야하므로 map을 통해 미리 저장해두도록 하자.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int seg[2000000];

void update(int node_index, int node_left, int node_right, int index){
    if(index < node_left || node_right < index) return;

    seg[node_index]++;
    if(node_left == node_right) return;
    int mid = (node_left + node_right) / 2;
    update(node_index * 2, node_left, mid, index);
    update(node_index * 2 + 1, mid + 1, node_right, index);
    return;
}

int query(int node_index, int node_left, int node_right, int query_right){
    int query_left = 1;
    if(query_right < node_left || node_right < query_left) return 0;
    if(query_left <= node_left && node_right <= query_right) return seg[node_index];

    int mid = (node_left + node_right) / 2;
    return query(node_index * 2, node_left, mid, query_right) +
           query(node_index * 2 + 1, mid + 1, node_right, query_right);    
}

int main(void){
    fastio;
    memset(seg, 0, sizeof(seg));
    vector<int> data_input;
    vector<int> sorted;
    data_input.push_back(-1); // 잉여 데이터(1 base)
    sorted.push_back(1000000001);
    map<int, int> index_set;
    
    int N;
    cin >> N;

    for(int i = 1; i <= N; i++){
        int t;
        cin >> t;
        data_input.push_back(t);
        sorted.push_back(t);
        index_set.insert(make_pair(t, i));
    }

    sort(sorted.begin(), sorted.end(), greater<int>());
    vector<int> result(N + 1);

    for(int i = 1; i <= N; i++){
        int rank = index_set[sorted[i]];
        result[rank] = query(1, 1, N, rank - 1) + 1;
        update(1, 1, N, rank);
    }

    for(int i = 1; i <= N; i++){
        cout << result[i] << "\n";
    }

    return 0;
}