백준 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

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 111111;
	#define ll long long
	ll N;
	vector<ll> arr[MAX];
	ll ans, tree[MAX];
	int Li(int x){
	return x&(-x);
	}
	ll sum(int i){
	ll temp = 0;
	while(i>0){
	temp += tree[i];
	i -= Li(i);
	}
	return temp;
	}
	void update(int i){
	while(i<=100001){
	tree[i] += 1LL;
	i += Li(i);
	}
	}
	bool cmp(const int &a, const int &b){
	return a > b;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (ll i = 1; i <= N; ++i){
	ll num;
	cin >> num;
	arr[num].push_back(i);
	}
	// 큰 수부터 볼꺼에요
	for (ll i = 100000; i > 0; i--){
	if(arr[i].empty()) continue;
	// 큰 수의 각 위치들 중 맨 뒤 위치부터 보자
	sort(arr[i].begin(),arr[i].end(),cmp);
	for(auto where: arr[i]){
	update(where);
	//앞에 있는 수 중 자신보다 큰 수의 개수
	ll leftcnt = sum(where-1);
	//뒤에 있는 수 중 자신보다 작은 수의 개수
	ll rightcnt = (N-where)-(sum(N)-sum(where));
	ans+=leftcnt*rightcnt;
	}
	}
	cout << ans << '\n';
	return 0;

view raw BOJ 5012.cpp hosted with ❤ by GitHub