백준(BOJ) 2517 달리기

sum함수에서
s~e 까지의 합 = tree[node]
구하고자하는 범위 l~r

먼저 실력을 등수로 매핑을 해야한다.
실력의 범위가 1 이상 1,000,000,000 이하라서 10억 배열을 선언할 수 없기 때문에

그 후 등수를 기준으로 세그트리를 활용한다.

트리를 0으로 세팅후 나의등수 p 보다  작은 1~p-1의 구간합을 구한다.

이때 구한 값이 내가 앞지를 수 있는 선수의 숫자이다.

그 후 등수 p (==idx)를 1로 update 해준다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <unordered_map>
#include <string>
using namespace std;
using pii = pair<int, int>;
using lld = long long int;
int n, m;
 
unordered_map<int, int> mp;
 
vector<lld> v;
vector<lld> tree;
lld a[500001];
 
lld sum(int node, int s, int e, int l, int r) {
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    int mid = (s + e) / 2;
    return sum(node*2, s, mid, l, r) + sum(node*2+1, mid + 1, e, l, r);
}
 
void update(int node, int s, int e, int idx, lld diff) {
    if (!(s<=idx && idx<=e)) return;
    tree[node] += diff;
    if (s != e) {
        int mid = (s + e) / 2;
        update(node * 2, s, mid, idx, diff);
        update(node * 2 + 1, mid + 1, e, idx, diff);
    }
 
}
 
int main() {
    scanf("%d", &n);
    tree = vector<lld>(n * 4, 0);
    
    v.push_back(-1);
    for (int i = 1; i <= n; i++) {
        lld x; scanf("%lld", &x);
        v.push_back(x);
        a[i] = x;
    }
 
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; i++) {
        mp[v[i]] = i;
    }
    
    for (int i = 1; i <= n; i++) {
 
        lld x = sum(1, 1, n, 1, mp[a[i]] - 1);
        printf("%lld\n", i - x);
        update(1, 1, n, mp[a[i]], 1);
 
    }
 
    return 0;
}