[백준 2517] 달리기

문제

www.acmicpc.net/problem/2517

 

알고리즘

세그먼트 트리, 좌표압축

 

풀이

현재 달리는 사람의 순서가 주어질 때, 자신의 최대등수를 출력하는 문제입니다. 자신보다 능력이 뛰어난 사람이 앞에 달리고 있으면 앞지를 수 없지만, 자신보다 능력이 낮은 사람이 앞에 달리고 있으면 앞지를 수도 있습니다.

 

쿼리는 달리는 순서대로 세그먼트트리를 업데이트 하며 그 순간 자신보다 앞에 있는 사람의 수를 묻고 있습니다. 누적합으로 자신앞에 있는 사람의 수를 알 수 있으므로 펜윅트리를 활용합시다. 유사한 문제가 많지만 그 문제들과 다른점은 주어지는 능력값이 굉장히 큰 수 라는 것입니다. 이는 좌표압축을 통해 해결가능합니다.

 

각 쿼리당 요구하는 시간복잡도는 $O(logN)$ 이므로 시간복잡도는 $O(NlogN)$ 입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

const int MAXS = 500'000;

int N,S;
int arr[MAXS + 1],fenwick[MAXS+1];
vector<int> vt;

int getidx(int val) {
    return lower_bound(vt.begin(), vt.begin() + S,val) - vt.begin()+1;
}

int query(int idx) {
    int ret = 0;
    while (idx) {
        ret += fenwick[idx];
        idx -= idx & -idx;
    }
    return ret;
}

void update(int idx, int val) {
    while (idx <= S) {
        fenwick[idx] += val;
        idx += idx & -idx;
    }
}

int main() {
    FAST;
    cin >> N;

    rep(i, N) {
        cin >> arr[i];
        vt.emplace_back(arr[i]);
    }
    sort(vt.begin(), vt.end());
    S = unique(vt.begin(), vt.end()) - vt.begin();

    rep(i, N) {
        int idx = getidx(arr[i]);
        update(idx, 1);
        int kth = query(S) - query(idx)+1;
        cout << kth << '\n';
    }

    return 0;
}