BOJ 2517 달리기

사용한 알고리즘

세그먼트 트리

알고리즘 설명

이 문제의 접근은 정말 재미있는 문제이다.
세그먼트 트리를 실력 값으로 접근하면 저장할 수 없다.
하지만 우리는 누가 더 앞서 갈 것인지에 대해서 크기 관계만 알면 된다.
앞에 있는 사람을 앞서 가기 위해서는 실력이 더 큰 경우이다.
이러한 관계로 실력 값을 등수로 바꾼다.
이후에 앞에서 부터 자기 실력 등수 보다 높으면서 앞에서 달리는 사람 수를 세그먼트 트리로 센다.
이를 출력한다. O(NlogN)

풀이

// baekjoon 2517 yechan
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
const int SIZE = 1<<19;
const int MAX_N = 500001;
struct Runner{
    int idx, perf;
    Runner():Runner(0,0){}
    Runner(int idx, int perf):idx(idx), perf(perf){}
    bool operator<(const Runner& O) {
        return idx < O.idx;
    }
};

bool perfcmp(const Runner &A, const Runner &O) {
    if (A.perf == O.perf) return A.idx < O.idx;
    return A.perf > O.perf;
}


int N;
Runner data[MAX_N];

int arr[SIZE*2];

struct SegTree{
    int sum(int L, int R, int nodeNum, int nodeL, int nodeR) {
        if (R < nodeL || nodeR < L) return 0;
        if (L <= nodeL && nodeR <= R) return arr[nodeNum];
        int mid = (nodeL + nodeR) / 2;
        return sum(L, R, nodeNum*2, nodeL, mid) + sum(L, R, nodeNum*2+1, mid+1, nodeR);
    }
    int sum(int L, int R) { return sum(L, R, 1, 0, SIZE-1); }

    void update(int i, int val) {
        i += SIZE;
        arr[i]=val;
        while (i > 1) {
            i /= 2;
            arr[i] = arr[i*2]+arr[i*2+1];
        }
    }
};

int main() {
    scanf("%d", &N);
    for (int i=1; i<=N; i++) {
        scanf("%d", &data[i].perf);
        data[i].idx=i;
    }
    sort(data+1, data+N+1, perfcmp);

    for (int i=1; i<=N; i++)
        data[i].perf=i;
    sort(data+1, data+N+1);

    SegTree sg;
    for (int i=1; i<=N; i++) {
        sg.update(data[i].perf, 1);
        printf("%d\n", sg.sum(1, data[i].perf));
    }
    return 0;
}