[C++] Counting Inversions (백준 10090번)

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

 

정리하자면 수열 a[1], a[2], ..., a[n] 에서, i < j 이면서 a[i] > a[j] 인 쌍의 개수를 찾는 문제이다.

이 문제의 포인트는 i < j 인 조건(앞에서 몇 번 나왔는지)을 별도의 인덱스로 처리하는 게 아니라, 입력 순서(=쿼리 순서) 자체가 그 역할을 하도록 하면 된다는 점이다. 

즉, 수열을 왼->오로 순회하면서, 현재 원소(= a[j])보다 큰 값(= a[i])이 그 앞에 몇개 있었는지를 세그먼트 트리에 저장하고 업데이트하고...를 반복하면 된다. (왼->오로 순회하기 때문에 j는 항상 i보다 크다.)

 

#include <iostream>
#include <vector>
using namespace std;

int MAXVAL = 1000000;
int n;

struct SegTree {
    vector<long long> tree;

    long long update(int idx, int l, int r, int target, long long val) {
        if (target < l || target > r) return tree[idx];
        if (l == r) return tree[idx] = val;
        int m = (l + r) / 2;
        return tree[idx] = update(idx * 2, l, m, target, val) + update(idx * 2 + 1, m + 1, r, target, val);
    }
    
    long long query(int idx, int l, int r, int wl, int wr) {
        if (wr < l || wl > r) return 0;
        if (wl <= l && wr >= r) return tree[idx];
        int m = (l + r) / 2;
        return query(idx * 2, l, m, wl, wr) + query(idx * 2 + 1, m + 1, r, wl, wr);
    }
    
    long long update(int target, long long val) {
        return update(1, 0, MAXVAL, target, val);
    }
    
    long long query(int wl, int wr) {
        return query(1, 0, MAXVAL, wl, wr);
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    SegTree seg;

    cin >> n;
    seg.tree.assign(4 * MAXVAL + 1, 0);

    for (int i = 1; i < MAXVAL + 1; i++) seg.update(i, 0);

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ans += seg.query(x + 1, MAXVAL);
        seg.update(x, seg.query(x, x) + 1);
    }

    cout << ans << '\n';
}

(AC)