Frosh Week (백준 4157)

안녕하세요. 오늘은 swap하는 횟수를 셀 거예요.

문제

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

아이디어

이 문제는 그냥 N(<=1,000,000)개의 수가 주어지면 i<j이고 Ai>Aj인 수의 개수를 세면 됩니다.
이는 세그먼트 트리로 쉽게 할 수 있습니다. 그런데 수의 범위는 안주어져있으므로 값 압축을 해야합니다.

소스코드

#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 update(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;
    update(s, mid, node * 2, idx);
    update(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());

    ll ans = 0;
    for (i = 0; i < N; i++)
    {
        v[i] = lower_bound(nums.begin(), nums.end(), v[i]) - nums.begin() + 1;
        ans += SUM(1, N, 1, v[i] + 1, N);
        update(1, N, 1, v[i]);
    }
    cout << ans; 
}

감사합니다.