[백준/BOJ/7578] 공장

세그먼트 트리 or 펜윅 트리를 사용해야 하는 문제다.

 

원리는 이와 같다.

입력

5 132 392 311 251 231 392 351 132 311 231

 

A 배열의 index 를 처음부터 찾아 나가면서, 그 뒤에 있는 구간 합을 result 에 더해주는 방식이다.

index	1	2	3	4	5	Result
A	132	392	311	351	231	0
B (Tree 의 IDX)	392	351	132	311	231	0
Tree [A[1]] --> Tree[3]	0	0	1	0	0	0+ Tree[4-5]
Tree [A[2]] --> Tree[1]	1	0	1	0	0	1 + Tree[2-5]
Tree[A[3]] --> Tree[4]	1	0	1	1	0	1 + Tree[5]
Tree[A[4] --> Tree[2]	1	1	1	1	0	3 + Tree[3-5]
Tree[A[5]] --> Tree[5]	1	1	1	1	1	3 + nothing

 

1) 펜윅 코드

#include <iostream>
#include <map>
using namespace std;
const int MAX = 5e5 + 1;
int N, tree[MAX], arr[MAX];
map<int, int> mp;
void update(int i,int val) {
	while (i <= N) {
		tree[i] += val;
		i += (i & -i);
	}
}
int sum(int i) {
	int ret = 0;
	while (i > 0) {
		ret += tree[i];
		i -= (i&-i);
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	for (int i = 1; i <= N; i++) {
		int num; cin >> num;
		mp[num] = i;
	}
	long long res = 0;
	for (int i = 1; i <= N; i++) {
		int lsum = sum(mp[arr[i]]);
		int rsum = sum(N);
		res += (rsum - lsum);
		update(mp[arr[i]], 1);
	}
	cout << res << "\n";
	return 0;
}

 

2) 세그 코드

#include <iostream>
#include <map>
using namespace std;
const int MAX = 5e5 + 1;
int N, arr[MAX], tree[MAX * 3];
map<int, int> mp;
int query(int node, int start, int end, int left,int right) {
	if (right<start || left>end) return 0;
	if (left <= start && end <= right) return tree[node];
	int lsum = query(node * 2, start, (start + end) / 2, left, right);
	int rsum = query(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
	return lsum + rsum;
}
void update(int node, int start, int end, int index, int value) {
	if (index<start || index>end) return;
	if (start == end) {
		tree[node] = value;
		return;
	}
	update(node * 2, start, (start + end) / 2, index, value);
	update(node * 2 + 1, (start + end) / 2 + 1, end, index, value);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	for (int i = 1; i <= N; i++) {
		int num; cin >> num;
		mp[num] = i;
	}
	long long res = 0;
	for (int i = 1; i <= N; i++) {		
		res += query(1, 1, MAX, mp[arr[i]] + 1, MAX);
		update(1, 1, MAX, mp[arr[i]], 1);
	}
	cout << res << "\n";
	return 0;
}

 

3) 성능 차이 (펜윅이 아래)