달리기 C++ - 백준 2517

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

세그먼트 트리 문제.

문제 접근

자신보다 앞에 달리고 있는 선수이면서, 자신보다 평소실력이 낮은 선수가

총 몇 명인지를 구하는 문제이다.

답이 ( 현재 등수 - 자신보다 앞에 달리고 있는 선수이면서, 자신보다 평소실력이 낮은 선수의 명수)

이므로 세그먼트 트리로 선수의 평소실력을 관리하면 된다.

그런데 평소 실력의 범위가 1이상 10억 이하이므로

일반 세그먼트 트리로는 관리할 수 없다.

$N$의 조건이 50만인 것을 감안하여

좌표 압축을 사용해 세그먼트 트리로 관리하면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define SIZE 500001*4 // 500001
typedef long long ll;
using namespace std;

int tree[SIZE];

void update(int X, int node, int S, int E){
    if(E<X || X<S) return;
    if(S==E){
        tree[node]++;
        return;
    }
    int MID=(S+E)/2;
    update(X,2*node,S,MID);
    update(X,2*node+1,MID+1,E);
    tree[node]=tree[2*node]+tree[2*node+1];
}

int query(int R, int node, int S, int E){
    if(R<=S) return 0;
    if(E<R) return tree[node];
    int MID=(S+E)/2;
    return query(R,2*node,S,MID)+query(R,2*node+1,MID+1,E);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &t:a) cin >> t;
    vector<int> b(a);
    sort(b.begin(),b.end());
    for(int i=0;i<n;i++){
        auto it=lower_bound(b.begin(),b.end(),a[i]);
        int t=it-b.begin()+1;
        update(t,1,1,n);
        cout << i+1-query(t,1,1,n) << '\n';
    }
    return 0;
}