BOJ 7578 공장

문제 태그: https://www.acmicpc.net/problem/7578

문제 소개

2열에 걸쳐 N개의 숫자가 주어진다. 윗줄과 아랫줄에 한쌍의 같은 숫자가 선으로 연결되어있다. 교차되는 선의 쌍의 수를 구하시오. 

문제 풀이

일단 같은 숫자끼리 (a,b)의 쌍을 만들어서 생각해보자. 우리는 N개의 (a,b)를 얻을 수 있으며 그중에 
i,j 에 대해 $a_{i} < b_{i}, a_{j} > b_{j} $ 또는 $a_{i} > b_{i}, a_{j} < b_{j} $를 만족하는 쌍의 갯수를 구하면 된다.
한 쌍의 두 값에 대해서 순서가 바뀌어있는 갯수를 세는 문제이며, 이를 흔히 inversion counting 문제라고 불린다. 
inversion counting 문제는 merge sort 혹은 segment tree를 이용해서 $O(NlgN)$에 풀 수 있음이 알려져 있고, 이 글에서는 segment tree를 활용하여 해결하는 방법을 말하려고 한다. 

방법은 간단하다.
1. a값의 순서대로 정렬한다.
2. b+1~n까지 구간합을 구한다.
3. b번째 위치에 1을 업데이트 한다.
4. 2번 행동에서 얻은 값을 모두 더한다.

이 방법이 왜 되는지 생각해보자. 2번 값을 구하는 시점 i에서 그 전에 업데이트가 된 애들은 a값이 $a_i$보다 작은 애들이다. 따라서 b값이 $b_i$보다 큰 애들의 숫자만 세서 다 더해주면 되고, 따라서 b+1부터 n까지의 구간 합을 구해서 더해주는 것이다. 

코드

#include <bits/stdc++.h>
using namespace std;
 
struct run{
    long long int  idx1,idx2;
};
 
bool sf1(run a,run b)
{
return a.idx1>b.idx1;
}
bool sf2(run a,run b)
{
return a.idx1<b.idx1;
}
 
 
run arr[500005];
run arr2[500005];
run arr3[500005];
long long int tree[1100005];
int n,m;
 
void update (int node,int start,int en,int index,long long int diff)
{
    if(index<start || index>en) return;
    tree[node] = tree[node]+diff;
    if(start!=en)
    {
        update( node*2,  start,(start+en)/2, index,diff);
        update( node*2+1,(start+en)/2+1,en, index,diff);
    }
}
 
long long sum(int node,int start,int en,int left,int right)
{
    if(left>en||right<start) return 0;
    if(left<=start && en<=right) return tree[node];
    return sum(node*2,start,(start+en)/2,left,right)+
           sum(node*2+1,(start+en)/2+1,en,left,right);
}
 
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&arr[i].idx1);
        arr[i].idx2=i;
    }
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&arr2[i].idx1);
        arr2[i].idx2=i;
    }
    sort(arr+1,arr+n+1,sf1);
    sort(arr2+1,arr2+1+n,sf1);
 
    for(i=1;i<=n;i++)
    {
        arr3[i].idx1=arr[i].idx2;
        arr3[i].idx2=arr2[i].idx2;
    }
    sort(arr3+1,arr3+n+1,sf2);
 
    long long int summ=0;
 
    for(i=1;i<=n;i++)
    {
        summ+=sum(1,1,n,arr3[i].idx2,n);
        update(1,1,n,arr3[i].idx2,1);
    }
    printf("%lld\n",summ);
}