[Segtree] BOJ 7578 공장

문제 링크 : www.acmicpc.net/problem/7578

7578번: 공장

케이블의 교차점은 어떤 조건에서 발생할까? 다음과 같은 예시를 통해 알아보자.

A열의 a번째 기계와 연결된 B열의 기계가 a'일 때, 이 기계와 케이블이 교차하기 위한 기계의 위치 (b, b')는 다음 조건을 만족한다.

"b < a AND b' > a' 또는 b > a AND b' < a"

이 두 조건 중 첫번째, b < a AND b' > a' 에 주목하자.

이 조건을 이용하면 우리는 두 열중 하나의 열을 순차적으로 탐색하며 해당 조건을 만족하는 기계의 갯수를 세어 문제를 해결할 수 있다.

이 풀이에서는는 위쪽 열(문제의 A열)의 기계를 순차적으로 살펴보며 발생하는 교차점을 세려고 한다.

우선 1번 기계에 대한 교차점은 다음과 같이 확인할 수 있다.

1번 기계에 대한 교차점

아직 1번 기계만 확인했으므로, 1번 기계와 케이블 교차가 발생하는 기계는 없다.

2번 기계에 대한 교차점

2번 기계를 확인했을 때, 2번 기계와 교차점이 발생하는 기계는 1번 기계이다.

A열의 1번 기계는 2번 기계의 앞 순서에 있고, B열의 1번 기계는 2번 기계의 뒤 순서에 있기 때문이다.

이번에는 3번 기계를 확인해보자.

3번 기계에 대한 교차점

3번 기계에 대해 교차점을 가지는 기계는 1번 기계이다.

마찬가지로 A열의 1번 기계는 3번 기계의 앞 순서에 있고, B열의 1번 기계는 3번 기계의 뒤 순서에 있기 때문이다.

2번 기계는 A열, B열 모두 3번 기계의 앞 순서에 있으므로, 교차점이 발생하지 않는다.

 

이를 통해 우리는 다음 사실을 알 수 있다.

A열의 k번째 기계에 대한 교차점 수는, 연결된 B열의 기계의 뒤 순서에 연결된 A열 1 ~ (k - 1)번째 기계들의 수와 같다.

A열의 기계를 순차적으로 확인하기 때문에, 교차점의 b < a 조건은 반드시 만족하게 된다. 따라서, b' > a' 인 기계들의 수를 세준다.

다시 말하면, A열의 번호 n인 기계에 대해, 그 이전에 확인한 B열의 기계들 중 B열의 n번 기계 이후에 등장하는 것들의 수를 세주면 된다.

단 문제에서 제시된 기계의 수가 50만개이기 때문에, 단순 카운팅으로는 시간 제한을 만족할 수 없다. 따라서, 세그먼트 트리를 이용한다.

세그먼트 트리(Segment Tree)

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <map>
 
#define MAX_SIZE 500000
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n;
int segtree[MAX_SIZE * 4];
int connect[500001];
map<int, int> dict;
 
void update(int node, int start, int end, int target) {
    if (start > target || end < target) return;
    if (start == end) {
        segtree[node] += 1;
        return;
    }
 
    segtree[node] += 1;
    int mid = (start + end) / 2;
    update(node * 2, start, mid, target);
    update(node * 2 + 1, mid + 1, end, target);
}
 
int query(int node, int start, int end, int left, int right) {
    //범위에 포함되지 않는 경우 0 반환
    if (end < left || start > right) return 0;
 
    //완전 포함될 경우 전체를 반환
    if (left <= start && end <= right) return segtree[node];
 
    //일부 포함될 경우 재귀
    int mid = (start + end) / 2;
    return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
}
 
ll get_answer() {
    ll answer = 0;
 
    for (int i = 1; i <= n; i++) {
        //연결된 기계 위치 확인
        int pos = connect[i];
 
        //pos 이후로 연결되어있는 기계의 갯수 확인
        answer += query(1, 1, n, pos + 1, n);
        
        //pos 위치에 대해 갱신
        update(1, 1, n, pos);
    }
 
    return answer;
}
 
void init() {
    int number;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> number;
        dict.insert({ number, i });
    }
 
    for (int i = 1; i <= n; i++) {
        cin >> number;
        int pos = dict[number];
        connect[pos] = i;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    ll answer = get_answer();
    printf("%lld\n", answer);
 
    return 0;
}