icpc.me 7578

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

공장에서 2N개의 기계가 2열에 걸쳐서 있고 각 열의 기계는 하나씩 짝을 이루어 케이블로 연결되어 있을 때, 교차하는 케이블 쌍의 개수를 구하는 문제입니다.

이 문제는 꽤 유명한 문제인 inversion 문제로, 어떤 배열 a가 주어졌을 때 i<j인 모든 i,j에 대하여 a[i]>a[j]인 i,j 쌍의 개수를 구하는 문제입니다. 문제를 조금 변경하여 A열의 기계를 왼쪽에서부터 1,2,3…으로 지정하고, 대응되는 B열의 기계가 같은 번호로 지정할 수 있습니다. 이때 B열의 배열에서 왼쪽 번호가 오른쪽 번호보다 큰 경우가 케이블이 교차하는 경우라는 사실을 알 수 있고, inversion 문제로 바꾸어 생각할 수 있게 됩니다.

inversion 문제를 조금 바꾸면 배열의 어떤 수 x에 대하여 x보다 오른쪽에 있는 수 중 x보다 작은 수의 개수를 세어 모두 더하는 문제로 생각할 수 있습니다. 다르게 말하면 x보다 작은 수의 개수에 x보다 왼쪽에 있는 수중 x보다 작은 수의 개수를 뺀 값을 구하여 모두 더하는 것과 같습니다. 여기서, x보다 왼쪽에 있는 수를 잘 저장해놓는다면 빠르게 문제를 해결할 수 있습니다. 어떻게 저장해야 빠르게 x보다 작은 수의 개수를 알 수 있을까요?

저장하고자 하는 수 y가 있을 때, 세그먼트 트리의 y번째에 1을 더하는 방식으로 저장하면 됩니다. 이렇게 저장한 후, 1부터 y까지의 구간합을 구하면 y보다 왼쪽에 있는 수 중 y보다 작은 수의 개수를 구할 수 있게 됩니다. 우리가 알고싶은 것은 y보다 오른쪽에 있는 수 중에서 y보다 작은 수이므로, sum(y)가 아닌 y-sum(y)를 구하여 모두 더하면 답을 알 수 있습니다.

inversion 문제를 병합정렬을 이용하여 해결하는 방법도 있지만, 이번에는 세그먼트 트리를 사용해서 풀었습니다. 이 문제에서는 구간의 최대 최소를 구하거나 구간에 업데이트를 하는 경우가 아니므로 코드가 더 간결한 펜윅 트리를 사용하였습니다. 또한 저장하고자 하는 수의 범위가 클 때(대충 1e9정도를 넘어갈 때) 좌표압축 기법을 사용하여 풀어야 하나, 이 문제는 배열에 저장된 값이 1000000 이하이므로 사용하지 않아도 괜찮습니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int bit[500005];
int ind[1000005];
ll sum(int i)
{
	ll ret=0;
	while(i)
	{
		ret+=bit[i];
		i-=(i&-i);
	}
	return ret;
}
void update(int i,ll val)
{
	while(i<=n)
	{
		bit[i]+=val;
		i+=(i&-i);
	}
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		ll x; cin>>x;
		ind[x]=i;
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		ll x; cin>>x;
		update(ind[x],1);
		ans+=ind[x]-sum(ind[x]);
	}
	printf("%lld",ans);
	return 0;
}