A Sorting Problem (백준 23336)

안녕하세요. 오늘은 정렬하는 문제를 풀 거예요.

문제

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

아이디어

전형적인 Inversion Counting 문제입니다.

소스코드

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

ll tree[808080] = { 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, ans = 0;
    cin >> N;
    for (i = 0; i < N; i++)
    {
        cin >> x;
        ans += SUM(1, N, 1, x + 1, N);
        change(1, N, 1, x);
    }
    cout << ans;
}

감사합니다.