[ 백준 ] 9463번 - 순열 그래프 (C++)

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

9463번: 순열 그래프

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

 

1. 첫 줄의 num을 입력받고, arr [ num ] = i로 저장합니다.

 

2. 두 번째 줄의 num을 입력받고, arr [ num ]을 idx로 세그먼트 트리를 갱신합니다.

 

3. arr [ num ] + 1부터 n까지 구간 합을 ans에 더해줍니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#define ll long long
 
using namespace std;
 
int T;
ll segTree[263000];
int arr[100001];
 
void updateTree(int node, int s, int e, int idx)
{
    if (s > idx || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx)
{
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int n;
        scanf("%d", &n);
        fill_n(segTree, 263000, 0);
        
        for (int i = 1; i <= n; i++) {
            int num;
            scanf("%d", &num);
            arr[num] = i;
        }
 
        ll ans = 0;
 
        for (int i = 1; i <= n; i++) {
            int num;
            scanf("%d", &num);
            updateTree(1, 1, n, arr[num]);
            ans += sumTree(1, 1, n, arr[num] + 1, n);
        }
 
        printf("%lld\n", ans);
    }
}