[BOJ 2517] 달리기

출처 : https://www.acmicpc.net/problem/2517

2517번: 달리기

 

세그먼트 트리(Segment Tree)를 이용한 문제이다. 

 

각 선수마다 자기보다 앞에 달리고 있는 선수들 중에서 자신보다 실력이 높은 사람의 수 + 1이 자신의 최선의 등수가 된다.  

각 선수들의 실력을 정수로 나타내었고, 실력의 범위가 1~10억이다. 

여기서 각 선수들의 실력이 모두 다르다고 하였고, 자신보다 실력이 높은 사람의 '수'만 구하면 되므로 

좌표압축 기법을 통해서 실력을 상대적인 값으로 바꿔준다. 

 

그 후, segment tree에 하나씩 추가해주면서 기존의 tree에 자신보다 높은 실력이 몇명있는지를 출력해주는 방식을 이용한다. 

 

#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<functional>
#include<string>
#include<vector>
#define ll long long int
#define INT_MAX 2147483647
#define MOD 1000000007
#define MAX 500000
 
using namespace std;
int arr[MAX + 1];
int temp[MAX + 1];
int tree[4 * MAX + 1];
 
void update(int idx, int s, int e, int i);
int sum(int idx, int s, int e, int l, int r);
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; cin >> N;
    int k;
    for (int i = 1; i <= N; i++) {
        cin >> k;
        temp[i] = k;
        arr[i] = k;
    }
    sort(temp + 1, temp + N + 1, greater<int>());
    for (int i = 1; i <= N; i++) {
        arr[i] = lower_bound(temp + 1, temp + N + 1, arr[i], greater<int>())- temp;
    }
    for (int i = 1; i <= N; i++) {
        cout << sum(1, 1, N, 1, arr[i])+1 << '\n';
        update(1, 1, N, arr[i]);
    }
 
}
 
void update(int idx, int s, int e, int i) {
    if (i < s || e < i) return;
 
    tree[idx]++;
    if (s != e) {
        update(idx<<1, s, (s + e) / 2, i);
        update((idx<<1) + 1, (s + e) / 2 + 1, e, i);
    }
}
int sum(int idx, int s, int e, int l, int r) {
    if (s > r || e < l) return 0;
    else if (s >= l && e <= r) return tree[idx];
    else return sum(idx<<1, s, (s + e) / 2, l, r) + sum((idx<<1)+1, (s + e) / 2+1, e, l, r);
}
 

33~36번째 줄이 좌표압축을 하는 과정이다.