[BOJ] 백준 7578 공장

출처: https://www.acmicpc.net/problem/7578

 Input 

5

132 392 311 351 231

392 351 132 311 231

　 

 Output 

3

A, B 배열이 주어졌을 때, 교차점의 개수를 어떻게 구할지 생각해야 합니다.

먼저 A배열을 모두 입력 받고, B 배열 원소를 한개씩 입력받을 때,

A 배열상 뛰쪽에 위치하는 숫자의 개수로 확인합니다.

① [392]: 숫자 외에는 존재하지 않으므로 +0

② [392 → 351]: A 배열에서 392는 351 앞쪽에 위치하므로 +0

③ [392 → 351 → 132]: 392, 351 두 개 모두 132보다 뒤에 위치하므로 +2

④ [392 → 351 → 132 → 311]: 351만 311보다 뒤에 위치하므로 +1

⑤ [392 → 351 → 132 → 311 → 231]: 231보다 뒤에 위치하는 것이 없으므로 +0

▶ 0 + 0 + 2 + 1 + 0 = 3

 

결국, B 배열 원소를 입력받으면서 A 배열상에서 뒤쪽에 위치한 개수를 파악해야 하는데,

N의 값이 크기 때문에 단순 탐색으로는 TLE 발생

일련의 식별번호로 구조를 단순화 해보자

A의 배열은 입력받은 순서대로 번호르 부여 ex) arr[392] = 1, arr[351] = 2

B 배열에서도 2 4 1 3 5 값을 변경해서 처리합니다.

이때, B 원소를 한개씩 입력 받을 때, 자기보다 큰 숫자가 몇개인지 확인하면 됩니다.

ex) [2, 4, 1] → 1보다 큰 숫자 [2, 4]로 +2개

ex) [2, 4, 1, 3] → 3보다 큰 숫자 [4]로 +1개

 

식별번호로 입력받은 숫자를 간소화하였지만 이는 Worst Case가 주어질 때,

N이 크기 때문에 마찬가지로 단순 탐색으로는 TLE 발생

결국 [2, 4, 1] 상태에서 기준 숫자 『1』에 대해서

[2, N]이 몇개 존재하는 상수시간 안에 확인이 가능해야 합니다.

즉, 기준 『X』가 주어질 때, 구간 [X+1, N]까지의 개수를 세그먼트 트리로 구합니다.

(단말 노드 값 = 1로 해서 구간 합 세그먼트 트리 이용)

 

단말 노드 1개가 변하면서 tree가 update 되는 것이기에

tree update 함수를 아래와 같이 구현 가능

(제출 코드에서는 구간을 update하는 코드로 작성되어 있음)

 

참고 코드

void update(int now, int s, int e, int val) {
    tree[now]++;
    if (s == e) return;
    int mid = (s + e) / 2;
    if (val <= mid) update(now * 2, s, mid, val);
    else update(now * 2 + 1, mid + 1, e, val);
}

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int N, arr[1000005], tree[1 << 20];
long long ans;
 
void initTree(int n, int s, int e) {
    if (s == e) {
        tree[n] = 0;
        return;
    }
    int L = n * 2, R = L + 1, mid = (s + e) / 2;
    initTree(L, s, mid);
    initTree(R, mid + 1, e);
    tree[n] = tree[L] + tree[R]; // 구간 합
}
 
int query(int now, int s, int e, int qs, int qe) {
    if ((qe < s) || (e < qs)) return 0;
    if ((qs <= s) && (e <= qe)) return tree[now];
    int L = now * 2, R = L + 1, mid = (s + e) / 2;
    return query(L, s, mid, qs, qe) + query(R, mid + 1, e, qs, qe);
}
 
void update(int now, int s, int e, int qs, int qe) {
    if ((qe < s) || (e < qs)) return;
    if (s == e) {
        tree[now]++;
        return;
    }
    int L = now * 2, R = L + 1, m = (s + e) / 2;
    update(L, s, m, qs, qe);
    update(R, m + 1, e, qs, qe);
    tree[now] = tree[L] + tree[R]; // 구간합
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    
    scanf("%d", &N);
    initTree(1, 1, N);
    
    int num;
    // A[] 값 입력
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &num);
        arr[num] = i;
    }
    
    // B[] 값 입력 받으면 tree 갱신, 구간 query
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &num);
        // [arr[num]+1, N] 개수
        ans += query(1, 1, N, arr[num]+1, N);
        // [arr[num], arr[num]] 구간 update
        // 즉, 단말 노드 상의 tree[arr[num]]++ 전체 트리가 update
        update(1, 1, N, arr[num], arr[num]);
    }
 
    printf("%lld\n", ans);
}