[C++] 4442번 빌보의 생일

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

---

 

26/02/22

 

 

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

---

 

문제 접근 방식:

 

 

첫번째로 주어진 사람들의 목록에 번호를 매기자.

문제에서 주어진 예시라면, Frodo에 $1$번, Sam에 $2$번, Bilbo에 $3$번을 매기는 것이다.

두번째로 주어진 사람들의 목록을 매긴 번호로 치환한다. 문제의 예시라면 Sam Frodo Bilbo순으로 주어져있으므로, $2\ 1\ 3$으로 바뀐다.

이후 바뀐 순열에 대해 인버전 카운팅 문제를 해결해주면 된다.

---

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

// 4442번 빌보의 생일
// 자료 구조, 세그먼트 트리, 집합과 맵
/*
접근 방법:
인버전 카운팅을 하는 문제다.

첫번째로 주어진 사람들의 목록에 번호를 매기자.

문제에서 주어진 예시라면, Frodo에 $1$번, Sam에 $2$번, Bilbo에 $3$번을 매기는 것이다.

두번째로 주어진 사람들의 목록을 매긴 번호로 치환한다. 문제의 예시라면 Sam Frodo Bilbo순으로 주어져있으므로, $2\ 1\ 3$으로 바뀐다.

이후 바뀐 순열에 대해 인버전 카운팅 문제를 해결해주면 된다.
*/
#include <iostream>
#include <vector>
#include <map>

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

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

    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 (r <= ql || qr <= l) return 0;
        return select(node<<1, l, (l+r)>>1, ql, qr)+select((node<<1)|1, (l+r)>>1, r, ql, qr);
    }

    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;
    }
};

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

int main(void){
    fastio

    int N;
    while (1){
        cin >> N;
        if (N == 0) break;
        solve(N);
    }
    return 0;
}