[백준 2517] 달리기 (C++)

2517번: 달리기

세그먼트 트리

---

최대 50만명의 선수들의 실력이 1부터 10억까지의 범위를 가지고 주어진다.

 

선수들의 등수는 상대적이므로 실력을 10억까지 되는수로 가지고 있을 필요가 없다.

정렬을 사용해서 선수들의 실력을 1~N까지의 수로 조정해준다.

 

그리고 주어진 선수들을 한명씩 세그먼트 트리에 넣으면서 자신보다 앞서 있지만 자신보다 실력이 낮은 선수의 수를 구한다.

세그먼트 트리의 구간은 선수들의 실력이 된다. 각 노드의 값은 해당 실력에 속한 선수들의 수가 된다.

트리를 탐색할 때 반드시 두 자식 구간중 하나로 탐색을 이어나갈 수 밖에 없다. 끝 구간보다 자신의 실력이 높다면 해당 구간의 값을 반환한다. logN을 얻을 수 있다.

 

그리고 자신보다 실력이 낮은 선수의 수를 구하고 자신을 트리에 입력한다. 트리에 입력하면서 자신이 지나는 구간의 값(자신이 해당되는 구간)을 1씩 증가시킨다. 

 

현재 달리기 순서 그대로 세그먼트 트리를 탐색하기 때문에 자신보다 뒤에 있는 경우를 생각할 필요가 없다.

 

세그먼트 트리문제를 풀다보니 DP와 비슷한 느낌을 받는다.

트리 노드 값의 의미와 트리 구간의 의미를 정하는게 정말 중요하다고 생각된다. DP도 DP배열의 의미만 올바르게 정하면 문제를 거의다 풀었다고 생각이 드는데 세그먼트 트리도 비슷한 느낌을 받았다. (사탕상자 문제 때도 비슷하게 느꼈다)

 

 

처음에 풀었던 방식이다. 시간초과가 났었고 위험한 방법이었다.

선수의 인덱스를 구간으로 설정했다. 트리의 노드마다 해당 구간의 최대, 최소 실력을 가지게 했다.

일단 문제는 전체 구간을 가지고 있는 트리의 1번노드에서 탐색을 시작하는데 처음부터 양쪽으로 갈라선다는 점이다.

따라서 logN이 불가능하고, 최대, 최솟값과 인덱스구간을 통해서 약간의 bound를 걸어주었지만 시간초과를 막을 순 없었다.

처음엔 logN이 아니더라도 충분히 탐색을 줄였다고 생각했고 내 어줍잖은 상상은 잘못된 논리를 정당화 시켜주었다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
#define MAX 500001
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N;
pii arr[MAX];
int tree[MAX * 4];
 
void input(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> arr[i].first;
        arr[i].second = i;
    }
}
 
int getRank(int startidx, int endidx, int node, int speed){
    if(speed > endidx){
        return tree[node];
    }
    if(startidx > speed || startidx == endidx) return 0;
    int mid = (startidx + endidx) / 2;
    return getRank(startidx, mid, node*2, speed) + getRank(mid+1, endidx, node*2+1, speed);
}
 
void insert_runner(int startidx, int endidx, int node, int speed){
    if(speed < startidx || speed > endidx) return;
    tree[node] += 1;
    if(startidx == endidx) return;
    int mid = (startidx + endidx) / 2;
    insert_runner(startidx, mid, node*2, speed);
    insert_runner(mid+1, endidx, node*2+1, speed);
}
 
bool cmp(pii &a, pii &b){
    return a.second < b.second;
}
 
void solve(){
    sort(arr+1, arr+N+1);
    for(int i = 1; i <= N; i++){
        arr[i].first = i;
    }
    sort(arr+1, arr+N+1, cmp);
    
    for(int i = 1; i <= N; i++){
        cout << i - getRank(1, N, 1, arr[i].first) << "\n";
        insert_runner(1, N, 1, arr[i].first);
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}