[2517] 달리기

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

와우.. 이 문제 진짜로~ 어렵네요!

진짜 가장 중요한 힌트는 달리기 실력을 상대적인 값으로 바꾸는 것입니다.

다른 분들이 푸신 방법들을 봐도 설명이 상세히 안나와있고.. 코드만 봤을 때는 잘 이해가 안가더라구요.

제가 푼 방법은 런타임 속도는 상대적으로 느리지만 좀 직관적으로 해결했습니다.

상대적으로 바꾸는 이유는 달리기 실력 값이 1 ~ 10^9까지 존재하기 때문에 이 값대로 트리를 형성할 수 없기 때문입니다.

우선 N은 3이상 5 * 10^5이므로 실력의 절대값으로 순위를 매겨서 상대적인 값으로 변환합니다.

순위를 매길 때 저는 정렬을 이용했습니다.

그리고 실력을 상대적인 값으로 바꾼 후에 다시 입력받은 순으로 정렬을 합니다.

그 다음에 트리를 생성하는데요!

세그먼트 트리이므로 tree(1 << ((int)ceil(log2(n)) + 1))!!!

이 뜻이 무엇이냐면 ceil이 어떤 값보다 크거나 같은 수를 찾는 함수인데요

예를 들어서 n = 1024라면 log2를 씌우면 10이라는 값이 나옵니다.

ceil(10)은 10이겠지요

1025를 넣는다면 10.xxxx가 나올 것입니다.

이것 또한 10이 나옵니다.!

무튼 ! 이렇게 해서 트리를 생성하면

for문을 n번 돌면서

나보다 큰 순위의 값이 존재하는지 검사를 해서

최선의 순위를 출력해주면 되는데요

최선의 순위 = 1 + (나보다 빨리 출발한 녀석들 중에 나보다 속도가 빠른녀석들)

입니다.

즉, 내 앞에 달리는 놈들 중에 나보다 빠른녀석들의 개수를 트리에 넣어야해요!

n = 8이라면

0~7까지의 실력 값이 존재합니다.

트리에 나보다 실력이 높은 놈의 수를 세서 1을 더하면 순위가 됩니다!

달리기 문제에서의 예제를 예로 들면

2, 8, 10, 7, 1, 9, 4, 15라는 절대 실력 값이 들어옵니다.

이것을 상대 실력으로 바꾸면

1, 4, 6, 3, 0, 5, 2, 7 이 됩니다!

첫번째 달리기 선수는 상대 실력이 1인데

맨앞에 달리고 있으므로 트리는 비어있습니다.

그러므로 1 + 0으로 최선의 순위는 1이됩니다.

두번쨰 선수! 상대 실력은 4입니다.

트리에는 현재 1의 값 밖에 존재하지 않습니다.

순위는 1 + 0 = 1이 됩니다.

3번째도 마찬가지겠지요.

4번째에서는 상대 실력이 3입니다.

현재 트리에는 3가지의 실력 값이 들어가있는데요.

나보다 큰 실력 값이 몇개인지 찾아야겠지요.

찾아보니 4, 6이라는 실력 값이 존재합니다.

그러므로 1 + 2를 해서 3이라는 최선의 순위를 찾을 수 있습니다.

세그먼트 트리에서 어떻게 자신보다 큰 실력 값을 찾는지는 코드를 통해서 보시기 바랍니다.

궁금한 점은 댓글 달아주시면 답변 드리겠습니다.

풀 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
 
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e6
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
pii arr[(int)5e5];//실력, 위치
 
int update(vi &tree, int node, int value, int start, int end) {
    if (value < start || end < value) return tree[node]; // 범위 벗어나면 그냥 리턴
    else if (start == end) return tree[node] = 1; // 내가 찾는 value이면 1리턴
 
    int mid = (start + end) / 2;
    return tree[node] = update(tree, node * 2, value, start, mid) + update(tree, node * 2 + 1, value, mid + 1, end);
}
 
int query(vi &tree, int node, int value, int start, int end) {
    if (value < start) return tree[node]; // 내가 찾는 value보다 시작점이 크면 그냥 tree의 개수를 리턴하면 됨.
    else if (end < value || start == end) return 0;
    // end가 나보다 작다는 것은 내 value보다 작으므로 개수를 세면 안됨.
    // 혹은 첫번째 if(value < start) 조건에 안걸렸으면 start == end가 같을 조건은 무조건 start==end가 나보다 작다는 것을 의미
    // 그러므로 0리턴
    
    int ret = 0;
    int mid = (start + end) / 2;
    return query(tree, node * 2, value, start, mid) + query(tree, node * 2 + 1, value, mid + 1, end);
}
 
bool cmp(pii a, pii b) {
    return a.second < b.second;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first;
        arr[i].second = i;
    }
 
    sort(arr, arr + n);
 
    for (int i = 0; i < n; i++) arr[i].first = i;
 
    sort(arr, arr + n, cmp);
 
    vi tree(1 << ((int)ceil(log2(n)) + 1)); // 구간에 데이터가 몇 개 있는지를 파악하는 트리
 
    for (int i = 0; i < n; i++) {
        cout << 1 + query(tree, 1, arr[i].first, 0, n - 1) << '\n';
        update(tree, 1, arr[i].first, 0, n - 1);
    }
    return 0;
}