[백준-2517] 달리기

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

시간 복잡도가 매우 중요한 문제이다. 일반적인 생각으로 매 선수가 들어올 때마다 앞에서 몇번째인지 찾기 위해서는 "기존 입력을 받는 n" * "자기보다 작은 선수들 찾기 n" 가 되어 n^2 으로 시간이 터져버린다.

때문에 이 문제를 풀기 위해서는 최소한 nlogn 의 로직으로 풀어야 한다. 즉, 이분탐색이나 logn 복잡도의 탐색 알고리즘이 필요하다. 이를 위해 세그먼트 트리를 사용할 수 있다.

로직은 다음과 같다.

1. 첫번째 선수 하나 들어왔을 때 세그먼트 트리에 체크해준다.
2. 두 번째 선수 부터는 세그먼트 트리에 업데이트 하기전 자기보다 작은 값까지 몇까지 있는지 logn의 복잡도로 확인한다.
3. 위 1, 2 번 방법을 반복한다.

즉, 세그먼트 트리에는 해당 값이 있는지 1로 체크만 해주고, 이에 따라 부분 합의 의미는 해당 범위까지 선수가 몇명있는지의 의미이다. 이를 통해 logn의 복잡도로 탐색할 수 있으며, 결국 nlogn 의 복잡도로 문제를 풀 수 있게 된다.

• 코드

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> 
#include <algorithm> 
#include <queue> 
#include <cstdio>
#include <tuple> 
#include <string> 
#include <string.h> 
#include <stack> 
#include <set>

using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
typedef tuple<int, int, string> tii;


LL n, m;
LL a, b;
vector<pii> v;
int tree[2000000];

int query(int node, int s, int e, int l, int r) {
    if (l > e || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    else {
        return query(node * 2, s, (s+e)/2, l, r) + query(node * 2 + 1, (s + e) / 2+1, e, l, r);
    }
}

void update(int node, int s, int e, int idx, int v) {
    if (idx < s || e < idx) return;
    if (s == e) tree[node] = v;
    else {
        update(node * 2, s, (s + e) / 2, idx, v);
        update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

bool compare(pii a, pii b) {
    return a.second  < b.second;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (LL i = 0; i < n; i++) {
        cin >> a;
        v.push_back({ i,a });
    }

    int res = 0;
    sort(v.begin(), v.end(), compare);
    for (int i = 0; i < v.size(); i++) {
        v[i].second = ++res;
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        int cnt = 0;
        int cur_power = v[i].second;

        if (cur_power > 1) {
            // 제일 작은 원소가 아니라면
            cnt = query(1, 1, res, 1, cur_power - 1);
        }
        update(1, 1, res, cur_power, 1);
        printf("%d\n", i + 1 - cnt);
    }


    return 0;
}
```