BOJ 2517 - 달리기 링크
(2023.05.02 기준 P4)

문제

현재 달리고 있는 선수 N명을 앞에서부터 평소 실력을 표시했을 때의 배열이 주어진다. 자기보다 앞에 달리고 있는 선수들 중 자기보다 평소 실력이 좋지 않으면 앞지르기가 가능하다.
이러한 가정 하에 각 선수마다 자신이 앞으로 얻을 수 있는 최선의 등수 출력

알고리즘

자신보다 평소 실력이 좋지 않은 선수를 전부 세야 하므로 세그먼트 트리

풀이

등수가 앞선 선수부터 평소 실력이 차례대로 주어진다.
앞지를 수 있는 선수는 자기보다 앞선 선수들이며 평소 실력이 좋지 않아야 한다.
그러므로 등수 차례대로 평소 실력인 인덱스에 1을 더하는 업데이트를 하며 자신의 등수보다 낮은 선수들을 구간합 쿼리로 받아 지금의 등수에서 빼면 된다.

그런데 이렇게 하려면 범위가 중요하다. 이 문제에서 범위는 1 이상 1,000,000,000 이하.
그대로 담으면 메모리가 터진다.
여기서 중요한 것은 선수의 수가 최대 500,000이다.
그러면 좌표 압축을 통해 0 ~ 499,999 범위로 만들어주면 충분히 세그먼트 트리를 이용할 수 있게 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int tree[1 << (int)ceil(log2(500000) + 1)];

// 좌표 압축
void compress(vector<int> &A){
    vector<int> B(A);
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    for (int &x: A) x = lower_bound(B.begin(), B.end(), x) - B.begin();
}

// 점 업데이트
void update(int node, int st, int en, int idx, int val){
    tree[node] += val;
    if (st != en){
        int mid = (st + en) >> 1;
        if (idx <= mid) update(node << 1, st, mid, idx, val);
        else update(node << 1 | 1, mid + 1, en, idx, val);
    }
}

// 구간합 쿼리
int query(int node, int st, int en, int left, int right){
    if (right < st || en < left) return 0;
    if (left <= st && en <= right) return tree[node];
    int mid = (st + en) >> 1;
    return query(node << 1, st, mid, left, right) + query(node << 1 | 1, mid + 1, en, left, right);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    vector<int> A;
    for (int i = 0, x; i < N; i++) cin >> x, A.push_back(x);
    compress(A);

    memset(tree, sizeof(tree), 0);
    for (int i = 0; i < N; i++){
        // 현재 등수까지의 선수들 중 평소 실력이 낮은 선수들의 수만큼 앞지를 수 있다.
        cout << i + 1 - query(1, 0, 499999, 0, A[i] - 1) << '\n';
        update(1, 0, 499999, A[i], 1);
    }
}

• Python (PyPy3)

import sys; input = sys.stdin.readline
from math import ceil, log2
from bisect import bisect_left

# 좌표 압축
def compress(A):
    B = sorted(set(A))
    return [bisect_left(B, x) for x in A]

# 점 업데이트
def update(node, start, end, idx, val):
    tree[node] += val
    if start != end:
        mid = (start + end) >> 1
        if idx <= mid:
            update(node << 1, start, mid, idx, val)
        else:
            update(node << 1 | 1, mid + 1, end, idx, val)

# 구간합 쿼리
def query(node, start, end, left, right):
    if right < start or end < left:
        return 0
    if left <= start and end <= right:
        return tree[node]
    mid = (start + end) >> 1
    return query(node << 1, start, mid, left, right) + query(node << 1 | 1, mid + 1, end, left, right)

N = int(input())
A = [int(input()) for _ in range(N)]
A = compress(A)

tree = [0] * (1 << ceil(log2(500000) + 1))
for i in range(N):
    # 현재 등수까지의 선수들 중 평소 실력이 낮은 선수들의 수만큼 앞지를 수 있다.
    print(i + 1 - query(1, 0, 499999, 0, A[i] - 1))
    update(1, 0, 499999, A[i], 1)