Array Manipulation at Moloco (Hard) (백준 15517)

안녕하세요. 오늘은 작은 수의 개수를 셀 거예요.

문제

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

아이디어

기본적으로 세그트리를 쓰면 됩니다.
하지만 수의 범위가 20억이기 때문에 값 압축을 해주어야합니다.
그리고 세그트리를 쓰려면 값들이 1 이상이여야하기 때문에 1씩 더해서 저장해 줍시다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll tree[4040404] = { 0 };
ll SUM(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}
void change(ll s, ll e, ll node, ll idx) //idx번지에 1추가하기
{
    if (e < idx || idx < s) return;
    tree[node]++;
    if (s == e) return;
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx);
    change(mid + 1, e, node * 2 + 1, idx);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, x;
    vector <ll> v, nums;

    cin >> N;
    for (i = 0; i < N; i++)
    {
        cin >> x;
        v.push_back(x);
        nums.push_back(x);
    }
    sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end());

    for (i = 0; i < N; i++) v[i] = lower_bound(nums.begin(), nums.end(), v[i]) - nums.begin() + 1; //세그트리를 위해 +1

    for (i = 0; i < N; i++)
    {
        cout << SUM(1, N, 1, 1, v[i] - 1) << "\n";
        change(1, N, 1, v[i]);
    }
}

감사합니다.