문제

문제 분석

가장 Naive 하게 생각해보자.
기계를 하나씩 연결해야할 것이다.
a[0]을 B열에 연결하고,
a[1]을 B열에 연결하고,
a[2]를 B열에 연결하고,...
하다보면, a[i]를 B열에 연결할 때, 도착점보다 오른쪽에 몇개의 점들이 들어왔는지 세면 교차점의 개수가 된다.
segment tree로 오른쪽 범위의 먼저 연결된 점들이 몇개인지 찾아주면 된다.

알고리즘

• Segment Tree

자료구조

• vector<int> st

결과

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

struct ST{
    vector<int> segTree;
    int h;
    int size;
};

const int MAX_ID = 1000000;
int N;

ST st;
vector<int> A;
vector<int> dst(MAX_ID+1, -1);

int UpdateST( int node, int l, int r, int idx );
int QueryST( int node, int l, int r, int tl, int tr );

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

    int64_t crossCount = 0;

    // Input
    cin >> N;
    A.resize(N);
    for ( int i = 0; i < N; i++ ){
        cin >> A[i];
    }
    for ( int i = 0; i < N; i++ ){
        int id;
        cin >> id;
        dst[id] = i;
    }

    // Build SegTree
    st.h = ceil(log2(N));
    st.size = (1<<(st.h+1))-1;
    st.segTree.resize(st.size, 0);

    // Calculate corssCount
    for ( int i = 0; i < N; i++ ){
        int id = A[i];
        int dstIdx = dst[id];
        crossCount += int64_t(QueryST( 0, 0, N-1, dstIdx+1, N-1));
        UpdateST(0, 0, N-1, dstIdx);
    }

    cout << crossCount;

    return 0;
}

int UpdateST( int node, int l, int r, int idx )
{
    if ( idx < l || r < idx ) 
        return st.segTree[node];
    if ( l == r && l == idx ){
        st.segTree[node] += 1;
        return st.segTree[node];
    }

    int mid = (r-l)/2 +l;
    int lRst = UpdateST(node*2+1, l, mid, idx);
    int rRst = UpdateST(node*2+2, mid+1, r, idx);

    st.segTree[node] = lRst + rRst;
    return st.segTree[node];
}

int QueryST( int node, int l, int r, int tl, int tr )
{
    if ( r < tl || tr < l )
        return 0;
    if  ( tl <= l && r <= tr )
        return st.segTree[node];

    int mid = (r-l)/2+l;
    int lRst = QueryST( node*2+1, l, mid, tl, tr );
    int rRst = QueryST(node*2+2, mid+1, r, tl, tr );

    return (lRst+rRst);
}

Other

항상 문제를 처음 마주할 때는, bruteforce 방식 더 나아가 손으로 상황을 세팅하는 것부터 생각해보자.
해당 부분에서 중요한 특징, 패턴을 찾자.