Ultra-QuickSort (백준 4297)

안녕하세요. 오늘은 울트라빠른정렬을 할 거예요.

문제

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

아이디어

그냥 Inversion Counting 문제입니다.
값/좌표 압축을 해서 수의 범위를 1부터 50만까지로 만든 다음에 세그먼트 트리를 이용해서 자신보다 앞에있는 수들 중 자신보다 큰 수의 개수를 세어주면 됩니다.

소스코드

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

ll tree[2020202] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return tree[node] = 0;
    ll mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
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, num;
    while (true)
    {
        cin >> N;
        if (N == 0) break;

        v.clear(); num.clear();
        for (i = 0; i < N; i++)
        {
            cin >> x;
            v.push_back(x); num.push_back(x);
        }
        sort(num.begin(), num.end());
        for (i = 0; i < N; i++)
            v[i] = lower_bound(num.begin(), num.end(), v[i]) - num.begin() + 1;

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

감사합니다.