[ 백준 ] 7578번 - 공장 (C++)

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

7578번: 공장

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 것을 추천드립니다!

https://rudalsd.tistory.com/51?category=1073064 

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

 

1. A라인의 값들을 입력받을 때 각 숫자들의 인덱스를 저장해줍니다.

 

2. B라인의 값들을 입력 받을 때 이미 입력된 값들 중 현재 인덱스보다 더 높은 인덱스에 있는 값들의 개수를 ans에 더해줍니다.

 

3. 세그먼트 트리를 업데이트해줍니다.

 

[ 소스 코드 ]

 

#include<iostream>
#include<cmath>
 
#define ll long long
 
using namespace std;
 
int N;
int A[1000001];
ll segTree[1111111];
 
ll getSum(int node, int start, int end, int sidx, int eidx)        //현재 idx값보다 큰 값들의 수를 return
{
    if (sidx > end || eidx < start) return 0;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = getSum(node * 2, start, mid, sidx, eidx);
    ll right = getSum(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
ll update(int node, int start, int end, int idx)        //현재 idx를 추가
{
    if (idx < start || idx > end) return segTree[node];
    segTree[node]++;
    if (start == end) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = update(node * 2, start, mid, idx);
    ll right = update(node * 2 + 1, mid + 1, end, idx);
 
    return segTree[node] = left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    ll ans = 0;
 
    for (int i = 1; i <= N; i++) {
        int num;
        scanf("%d", &num);
        A[num] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        int num;
        scanf("%d", &num);
        int idx = A[num];
        ans += getSum(1, 1, N, idx + 1, N);    //현재 idx보다 큰 값들의 수를 ans에 더하기
        update(1, 1, N, idx);    //현재 idx값을 넣어주기
    }
 
    printf("%lld", ans);
}