백준 7578 공장

 

이 문제는 공장 기계끼리 연결 했을 때 교차점을 세야 하는 문제입니다.

 

이게 예제 그림을 보고 또 자기가 만들어서 보면서 생각해보면 교차점이 생기는 조건을 알 수 있는데

 

위에 기계를 순서대로 1,2,3,4,5 ... 라고 순서를 정한뒤

아래 기계에 맞게 번호를 주게되면 예제 그림에선 아래와 같습니다.

 

1 2 3 4 5

2 4 1 3 5

 

이경우 아래 기계를 기준으로 보면 현재 나보다 앞에 있는 기계중 숫자가 큰 기계 개수만큼 교차점이 생김을 알 수 있습니다. 2 - 0개  4 - 0 개  1 - 2(앞에 2,4)개 3(앞에 4) - 1개 5 - 0개 즉 내 차례때 내 앞에 나보다 큰 수가 몇개 인지 알면 답을 찾을 수 있습니다. N<=500000 이므로 당연히 일일이 세는건 불가능하고 이럴 때 사용 할 수 있는 세그트리가 있죠. 세그트리를 이용해서 기계를 순서대로 지나며 나보다 큰 구간에서 sum을 구해주고 나를 포함시키는 update을 해주면서 진행하면 쉽게 해결되는 문제입니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <map>

#define MAX 500000
using namespace std;

long long tree[MAX * 4];
map<int, int> m;
int arr2[MAX + 1];

long long sum(int node, int start, int end, int left, int right) {
	if (left > end || right < start) return 0;
	else if (left <= start&&end <= right) return tree[node];

	int mid = (start + end) / 2;

	return sum(node * 2, start, mid, left, right) + sum(node * 2 + 1, mid + 1, end, left, right);
}

void update(int node, int start, int end, int diff, int index) {
	if (index < start || index > end) return;

	tree[node] += diff;
	if (start != end) {
		int mid = (start + end) / 2;
		update(node * 2, start, mid, diff, index);
		update(node * 2 + 1, mid + 1, end, diff, index);
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		m[x] = i;
	}

	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		arr2[i] = m[x];
	}

	long long ans = 0;
	for (int i = 0; i < N; i++) {
		ans += sum(1, 0, N - 1, arr2[i]+1, N-1);
		update(1, 0, N - 1, 1, arr2[i]);
	}
	cout << ans;
	return 0;
}