[ICPC] 백준 9463 - 순열 그래프

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

 

각 편에서 번호가 같은 정점끼리 연결했을 때 생기는 교차점으로 순열 그래프를 구성한다고 한다.

 

우리는 교차점의 개수를 구해야 되므로 문제에서 첫번째 그림을 보고 3770번 문제와 같은 흐름으로 inversion counting을 생각할 수 있다.

 

다만 이 문제는 주어진 입력에서 번호가 같은 정점끼리 연결하는 것이므로 이를 적절히 변환해줄 필요가 있다.

 

주어지는 첫번째 노드 집합을 index에 매칭하여 각 숫자가 어느 index에 대응하는지 배열로 저장한다.(mp[val] = idx)

 

두번째 노드집합에서는 index와 첫번재 mp배열에서 해당 노드 숫자의 index를 가져와 pair로 짝지어서 배열이나 선형 자료구조에 저장한다.

 

그렇게 되면 3770번과 같은 형태로 pair 배열을 구성할 수 있고 inversion counting을 해서 답을 구할 수 있다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int t;

ll fenwick[100001];
int mp[100001];

void add(int idx, int val)
{
    while (idx <= 1e5)
    {
        fenwick[idx] += val;
        idx += (idx & -idx);
    }
}

ll sum(int idx)
{
    ll ret = 0;

    while (idx > 0)
    {
        ret += fenwick[idx];
        idx &= (idx - 1);
    }

    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--)
    {
        ll res = 0;
        memset(fenwick, 0, sizeof fenwick);
        int n;
        cin >> n;

        int idx = 1;

        for (int i = 0; i < n; ++i)
        {
            int x;
            cin >> x;
            mp[x] = idx++;
        }

        vector<pii> v;

        for (int j = 1; j <= n; ++j)
        {
            int x;
            cin >> x;
            v.push_back({j, mp[x]});
        }

        sort(v.begin(), v.end());

        for (int k = n - 1; k >= 0; --k)
        {
            res += sum(v[k].second - 1);
            add(v[k].second, 1);
        }

        cout << res << '\n';
    }
}