[BOJ/Platinum 5] 백준 10090 Counting Inversions(C++)

문제 링크

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

10090번: Counting Inversions

 

문제

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.

입력

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces.

출력

Write the count of inversions on the standard output.

제한

• 2 ≤ n ≤ 1000000

예제 입력 1

7
4 2 7 1 5 6 3

예제 출력 1

10

알고리즘 분류

• 자료 구조

풀이

세그먼트 트리에 i번째 수 X를 추가하고 X 이전에 나왔던 수 X-1개 중 X보다 작은 수의 개수를 빼면 X 이전에 나왔던 수 중 X보다 큰 수의 개수가 나오게 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1000001
#define LL long long
#define INF 1e9

using namespace std;
int N;
LL MAP[MAX];
vector<int> SegTree;
LL answer = 0;

// Inversion Counting

void Init() {
	int Tree_Height = (int)ceil(log2(N));
	int Tree_Size = (1 << (Tree_Height + 1));
	SegTree.resize(Tree_Size);
}

void Update_SegTree(int Node, int S, int E, LL Val, LL Diff) {
	if (S == E) {
		SegTree[Node] += Diff;
		return;
	}
	int M = (S + E) / 2;
	if (Val <= M) {
		Update_SegTree(Node * 2, S, M, Val, Diff);
	}
	else {
		Update_SegTree(Node * 2 + 1, M + 1, E, Val, Diff);
	}
	SegTree[Node] = SegTree[Node * 2] + SegTree[Node * 2 + 1];
}

LL Find_Value(int Node, int S, int E, int Left, int Right) {
	if ((S > Right) || (Left > E)) {
		return 0;
	}
	if ((Left <= S) && (E <= Right)) {
		return SegTree[Node];
	}
	int M = (S + E) / 2;
	return Find_Value(Node * 2, S, M, Left, Right) + Find_Value(Node * 2 + 1, M + 1, E, Left, Right);
}

void Find_Answer() {
	cin >> N;
	Init();
	for (int i = 1; i <= N; i++) {
		int X;
		cin >> X;
		answer += (X - 1) - Find_Value(1, 1, N, 1, X - 1);
		Update_SegTree(1, 1, N, X, 1);
	}
	cout << answer << "\n";
}

int main() {
	FASTIO
	Find_Answer();

	return 0;
}