BOJ)10090 Counting Inversions

문제: icpc.me/10090

1~N의 숫자들로 구성 된 수열이 주어질 때 먼저 나온 수보다 늦게 나온 수가  더 작은 경우의 수를 구하는 문제이다.

N이 100만이기 때문에 N^2 완전 탐색으로 해결하기에는 문제가 있다.

따라서 우리는 쿼리를 받는 순서대로 온라인으로 처리를 해줄 것이다.

우선 내가 현재 보는 수가 x라면 나보다 작은 수의 개수는 x-1개다 그러면 나보다 먼저 나온 수들 중 나보다 작은 수의 개수가 a개라면

x에 의하여 결정되는 경우의 수는 x-1-a가 된다.

따라서 우리는 세그먼트 트리를 이용하여 수열을 받을때마다 x보다 작은 수의 개수들을 구해주어 x-1-a를 답에 더해주고 x의 위치에 1을 업데이트 시켜주면 된다.

주의 할점은 답을 저장할 자료형을 long long으로 사용해야 한다는 것이다.

#include <cstdio>
#include <algorithm>
#define MAX_N 1000000
using namespace std;
int seg[4 * MAX_N], x, n;
long long r;
int update(int pos, int node, int x, int y) {
    if (pos < x || y < pos)return seg[node];
    if (x == y)return seg[node] += 1;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, node * 2, x, mid) + update(pos, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        r += (long long)(x - 1 - query(1, x - 1, 1, 1, n));
        update(x, 1, 1, n);
    }
    printf("%lld\n", r);
    return 0;
}