불만 정렬 (백준 5012)

안녕하세요. 오늘은 불만을 가질거예요.

문제

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

아이디어

어떤 j에 대하여 1≤i≤j이고 Ai>Aj인 i의 개수를 Left[j], 반대로 j≤k≤N이고 Aj>Ak인 k의 개수를 Right[j]라고 하면 Left[i]*Right[i]의 모든 값들의 합을 구해주면 됩니다.

소스코드

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

ll tree[404040] = { 0 };
int init(int s, int e, int node)
{
    if (s == e) return tree[node] = 0;
    int mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
void change(int s, int e, int node, int idx) //idx에 1 더하기
{
    if (idx < s || e < idx) return;
    tree[node]++;
    if (s == e) return;

    int mid = (s + e) / 2;
    change(s, mid, node * 2, idx);
    change(mid + 1, e, node * 2 + 1, idx);
}
ll SUM(int s, int e, int node, 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(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}

ll Left[101010] = { 0 }, Right[101010] = { 0 }, num[101010] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, x, ans = 0;

    cin >> N;
    for (i = 1; i <= N; i++) cin >> num[i];
    for (i = 1; i <= N; i++)
    {
        Left[i] = SUM(1, N, 1, num[i] + 1, N);
        change(1, N, 1, num[i]);
    }
    init(1, N, 1);
    for (i = N; i >= 1; i--)
    {
        Right[i] = SUM(1, N, 1, 1, num[i] - 1);
        change(1, N, 1, num[i]);
    }
    for (i = 1; i <= N; i++) ans += Left[i] * Right[i];
    cout << ans;
}

감사합니다.