[백준/BOJ] 백준 7578번 : 공장

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

7578번: 공장

a열의 순서대로 숫자를 확인하면서 [b열에서 해당 숫자의 위치~n-1(b열의 끝)]사이에 체크된 것(a열 해당 숫자 이전에 체크된 것)의 개수를 세고, b열에서 해당 숫자의 위치를 체크하는 방법을 통해 문제를 해결했다. 해당 구간의 개수를 세고, 위치를 체크하는 방법은 세그먼트 트리를 이용했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> a;
vector<int> b_number_index(1000005); //b열에 해당 숫자가 어떤 인덱스에 있는지
vector<int> sgmtt(4000005, 0);
long long result = 0;

int UpdateSgmtt(int here, int range_left, int range_right, int update_index, int value)
{
	if (range_left == range_right && range_right == update_index)
		return sgmtt[here] = value;

	if (update_index < range_left || range_right < update_index)
		return sgmtt[here];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (range_left + range_right) / 2;

	return sgmtt[here] = UpdateSgmtt(left_child, range_left, mid, update_index, value) + UpdateSgmtt(right_child, mid + 1, range_right, update_index, value);
}

int QuerySgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_left <= range_left && range_right <= find_right)
		return sgmtt[here];

	if (find_right < range_left || range_right < find_left)
		return 0;

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (range_left + range_right) / 2;

	return QuerySgmtt(left_child, range_left, mid, find_left, find_right) + QuerySgmtt(right_child, mid + 1, range_right, find_left, find_right);
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		a.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		b_number_index[input] = i;
	}

	for (int i = 0; i < n; i++)
	{
		int a_value = a[i];

		//b열에서 b_number_index[a_value]~n-1사이에 이전에 체크한 것의 개수를 더한다
		//이전에 체크한것은 a열에서 앞서서 있는것이므로 a열에서 앞서서 있는게 b열에서는 뒤에 있으면 교차가 발생한다
		result += (long long)QuerySgmtt(0, 0, n - 1, b_number_index[a_value], n - 1);

		//해당 위치를 체크한다
		UpdateSgmtt(0, 0, n - 1, b_number_index[a_value], 1);
	}

	cout << result << "\n";

	return 0;
}