BOJ 7578 공장

사용한 알고리즘

LIS, 세그먼트 트리

알고리즘 설명

A 공장과 B 공장이 주어졌을때, 두 배열을 저장하여 정렬을 시킨다.
두 공장은 연결 관계에 있으므로 정렬 뒤에 A(i) == B(i)일 것이다.
이를 이용하여 본래 data(A(i)번째의 본래 위치) = B(i)의 본래 위치 형태로 data를 정렬 시켜 A 공장의 앞에서부터 B의 몇번째와 연결 되어 있는지 정보를 저장할 수 있다.
위에서 교차하지 않는 조건은 임의에 두 공장 i, j에 대해서 (A_i < A_j && B_i < B_j) 또는 (A_i > A_j && B_i > B_j)를 만족해야한다.
여기서 이미 A 공장은 i < j 라면 A_i < A_j를 만족한다 고로 우리는 B_i > B_j를 만족하면 교차한다는 것을 알 수 있다.
이러한 점에서 B_i 값을 세그먼트 트리에 적어놓은 이후, B_i 보다 큰 값을 가졌던 공장 수를 세그먼트 트리로 계산하면 이 값이 교차 횟수이며, 이를 계속 축적한다.

풀이

// baekjoon 7578 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=500001;
const int SIZE=1<<19;

int N, data[MAX_N], arr[SIZE*2];
pair<int,int> left[MAX_N], right[MAX_N];

// 세그먼트 트리
void update(int i, int val) {
	i += SIZE;
	arr[i] = val;
	while (i > 1) {
		i/=2;
		arr[i] = arr[i*2] + arr[i*2+1];
	}
}

int sum(int left, int right, int nodeNum, int nodeL, int nodeR) {
	if (right < nodeL || nodeR < left) return 0;
	if (left <= nodeL && nodeR <= right) return arr[nodeNum];
	int mid = (nodeL + nodeR)/2;
	return sum(left, right, nodeNum*2, nodeL, mid) + sum(left, right, nodeNum*2+1, mid+1, nodeR);
}

int sum(int left, int right) {
	return sum(left, right, 1, 0, SIZE-1);
}

int main() {
	scanf("%d", &N);
// 공장입력 받고 정렬하기
	for (int i=0; i<N; i++) {
		scanf("%d", &left[i].first);
		left[i].second = i;
	}
	for (int i=0; i<N; i++) {
		scanf("%d", &right[i].first);
		right[i].second = i;
	}
	sort(left, left+N);
	sort(right, right+N);

// A의 i번째 공장이 대응 되는 B의 위치는 data(i)에 저장됨
	for (int i=0; i<N; i++) {
		data[left[i].second] = right[i].second;
	}

	long long ret = 0;
	for (int i=0; i<N; i++) {
// 교차점 개수 세기
		ret += sum(data[i], MAX_N);
// 현재 위치 세그먼트 트리에 업데이트 진행
		update(data[i], 1);
	}
	printf("%lld\n", ret);
	return 0;
}