[PS] 백준 #10090. Counting Inversions

문제 정보

• 난이도: 플래티넘 V
• 문제 주소: https://www.acmicpc.net/problem/10090
• 이 문제를 푼 이유: 알고리즘 스터디 - 세그먼트 트리

 

문제

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Write program invcnt that computes the number of the inversions in a given permutation.

 

나의 풀이

스터디에서 배운 세그먼트 트리 코드를 사용해서 푼 문제이다. 이 문제는 알고리즘 분류를 보지 않고, 세그먼트 트리라는걸 모르는채로 풀면 $O(n^2)$ 풀이 이외에는 떠올리기가 쉽지 않았을 것 같다. 기본적인 아이디어는 아래와 같다.

숫자 k 차례일 때 지금까지 입력되었던 수들 중 k보다 큰 값이 몇개였는지를 구해서 매 쿼리마다 sum에 더하면 된다!

그런데 "지금까지 입력되었던 수들"을 어떻게 처리해야 할지는 잘 떠오르지 않아서 한참을 고민했다. 이 부분은 구글링을 통해 힌트를 살짝 얻었는데, 0으로 초기화된 세그먼트 트리에 지금까지 들어왔던 값들을 하나씩 1로 바꿔서 매 쿼리마다 세그먼트 트리를 업데이트하는 아이디어를 알게 되었다. 세그먼트 트리의 구현은 스터디에서 배운 것을 활용하였다. - 코드 출처: https://codeforces.com/blog/entry/18051

1. Build: 이 문제는 초기값이 모두 0으로 주어진 세그먼트 트리이기 때문에 배열의 초기화를 하면 Build가 끝난다.
2. query(l, r): l이상 r미만의 값을 모두 더해서 반환한다. (부분합 문제와 동일)
3. update(idx, value): idx 번째 값을 value로 바꾼 뒤 세그먼트 트리에서의 부모들을 업데이트한다.
4. 매 쿼리마다 ans에 query 값 더하기, 해당 값을 세그먼트 트리에 업데이트하기를 반복한다. 

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> tree;

void update(int idx, int value) {
    for (tree[idx += n] = value; idx > 1; idx >>= 1)
        tree[idx >> 1] = tree[idx] + tree[idx ^ 1];
}

long long query(int l, int r) {
    // sum interval [l, r)
    long long ret = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l % 2) ret += tree[l++];
        if (r % 2) ret += tree[--r];
    }
    return ret;
}

int main() {
    cin.tie(NULL);	cout.tie(NULL);	std::ios::sync_with_stdio(false);

    cin >> n;
    tree.resize(4 * n + 1, 0);
    vector<int> vec(n);
    for (int i = 0; i < n; i++) cin >> vec[i];

    // Make Segment Tree : default는 모두 0으로 초기화

    // Find Answer
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += query(vec[i] + 1, n+1);
        update(vec[i], 1);
        //cout << ans << " ";
    }
    cout << ans;
}