[백준] 공장 7578번 C++ 풀이

https://www.acmicpc.net/problem/7578

7578번: 공장

#include <iostream>
using namespace std;
int N;
int A[500001];
int B[1000001];
int Tree[500001*4];

long long sum(int node, int start, int end, int left, int right)
{ // 도착점+1부터 끝까지 케이블 몇개 교차되는지 확인해주기
	if (end<left || start>right)
		return 0;

	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 idx) // 케이블 내려온거 표시해주기
{
	if (start > idx || end < idx)
		return;
	if (start == end)
	{
		Tree[node] = 1;
		return;
	}
	int mid = (start + end) / 2;
	update(node * 2, start, mid, idx);
	update(node * 2 + 1, mid + 1, end, idx);
	Tree[node] = Tree[node * 2] + Tree[node * 2 + 1];


}

int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		B[num] = i;
	}

	long long res = 0;
	for (int i = 0; i < N; i++)
	{
		res += sum(1, 0, N - 1, B[A[i]]+1, N - 1);
		update(1, 0, N - 1, B[A[i]]);

	}
	cout << res;


}

A[i]를 A에서 i의 위치, B[i]를 B에서 i의 위치라고 하면 임의의 j에 대해

A[i]<A[j]

B[j]<B[i] 가 성립하면 교차점이 생긴다.

A[i]<A[j] 이 조건은 그냥 1~N번째까지 순서대로 반복문을 통해

교차점의 개수를 갱신해 나가면 된다.

A의 케이블을 타고가면 B위치가 나오는데 B에서의 위치+1에서부터 N까지 연결된 케이블 합이 i번째에서 생기는 교차점의 개수이다.

이 원리와 세그먼트 트리를 이용해서 제한시간 내에 문제가 풀이가 가능하다.

https://foxtrotin.tistory.com/164 이 블로그의 원리 설명이 도움이 되었다.

그냥 위의 초록색의 점 케이블을 타고 아래의 초록점에 도착하면 그 도착점+1부터 연결된 케이블이 존재하는 개수만큼

교차점(크로스)가 생기는 원리이다.

도착점+1부터 교차점 개수를 찾고, 아래 초록색 도착점에 위의 초록점에서 내려와 케이블이 하나 연결이 되어있다는것을 표시하면 된다. ( Tree[node] = 1 로 표시했다 )