[C++] 9463번 순열 그래프

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

---

 

26/02/21

 

 

인버전 카운팅을 하는 문제다.

---

 

문제 접근 방식:

 

 

첫번째로 주어진 순열이 $1\ 2\ 3\ \dots N$에 매핑된다고 간주하자.

즉, 예제 입력 1의 첫번째 테스트 케이스를 예시로 들자면 $2\ 5\ 4\ 1\ 3$을 $1\ 2\ 3\ 4\ 5$로 간주하자는 뜻이다.

즉, $2$를 $1$로, $5$를 $2$로, ... 그렇게 모든 수를 각각의 수로 간주하자.

이후 두번째로 주어진 순열을 매핑된 수로 바꾸면, 주어진 순열에 대한 인버전 카운팅을 세는 문제로 바꿀 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 9463번 순열 그래프
// 자료 구조, 세그먼트 트리 (카운팅 인버전)
#include <iostream>
#include <vector>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

struct Segtree{
    int N;
    vector<long long> tree;
    Segtree(int dataSize) : N(dataSize), tree(4*dataSize, 0) {};

    void build(const vector<long long>& arr){build(1, 0, N, arr);}
    void build(int node, int l, int r, const vector<long long>& arr){
        if (l+1 == r){
            tree[node] = arr[l];
            return;
        }
        build(node << 1, l, (l+r)>>1, arr);
        build((node << 1) | 1, (l+r)>>1, r, arr);
        tree[node] = tree[node<<1] + tree[(node << 1)|1];
        return;
    }

    void update(int idx, long long val){update(1, 0, N, idx, val);}
    void update(int node, int l, int r, int idx, long long val){
        if (idx < l || r <= idx) return;
        if (l+1 == r){
            tree[node] = val;
            return;
        }
        update(node << 1, l, (l+r)>>1, idx, val);
        update((node << 1)|1, (l+r)>>1, r, idx, val);
        tree[node] = tree[node << 1] + tree[(node << 1)|1];
        return;
    }

    long long select(int ql, int qr){return select(1, 0, N, ql, qr);}
    long long select(int node, int l, int r, int ql, int qr){
        if (ql <= l && r <= qr) return tree[node];
        if (qr <= l || r <= ql) return 0;
        return select(node << 1, l, (l+r)>>1, ql, qr) + select((node << 1)|1, (l+r)>>1, r, ql, qr);
    }
};

void solve(void){
    int N; cin >> N;
    vector<int> mapping(N+1, 0);
    int a;
    for (int i = 1; i < N+1; ++i){
        cin >> a; mapping[a] = i;
    }
    Segtree segtree(N+1);
    long long ans = 0;
    for (int i = 1; i < N+1; ++i){
        cin >> a;
        segtree.update(mapping[a], 1);
        ans += segtree.select(mapping[a]+1, N+1);
    }
    cout << ans << endl;
}

int main(void){
    fastio

    int T; cin >> T;
    while (T--){
        solve();
    }
    return 0;
}