백준 5012번 불만 정렬

문제링크: https://www.acmicpc.net/problem/5012

사용한 알고리즘: 펜윅트리


3쌍으로 되는 inversion의 개수를 구하는 문제였습니다.
펜윅트리를 이용하여 i번째 수를 볼 때, 앞쪽에 있는 큰 수의 개수, 뒷쪽에 있는 작은 수 의 개수를 확인하며 풀어주었습니다.

풀이는 다음과 같습니다.
(1) 벡터 배열을 하나 만들어서 입력을 받을 때 마다 그 수의 위치를 저장해주었습니다.

(2) 큰 수부터 차례로 보면서 펜윅트리를 구현해주었습니다. ( 큰 수가 i 번째 위치에 있다고 하면 i번째 부터 끝까지 +1 을 하는 펜윅 트리를 만들어서 이후 그보다 작은 수를 볼 때 (j번째라고 합시다.) 1~j-1번째까지 쌓인 +1들의 합은 j 앞에 있는 이보다 큰수들의 개수의 합이고,  j+1~N번째 있는 +1들의 합을 N-j에서 빼주면 그것이 j 뒤에 있는 이보다 작은수들의 개수의 합입니다.

(3) i번째에 위치한 숫자를 볼 때 생길 수 있는 3쌍의 inversion의 수는, 과정 (2)에 의하여 앞에 있는 큰 수들의 개수의 합: sum(i-1) 과 뒤에 있는 작은 수들의 개수의 합: (N-j)-(sum(N)-sum(j) 을 곱해주면 구할 수 있습니다.

펜윅트리를 이용하면 비교적 간단하게 풀 수 있는 문제였습니다.
혹시 펜윅트리에대한 자세한 내용이 궁금한 분들은 아래 링크에 잘 정리되어 잇으니 참고해주세요.
https://www.acmicpc.net/blog/view/21