백준 7578번 공장 문제

일단 실제로 트리가 어떻게 생겼는지부터 그려봤다

일단 A열 첫 번째 같은 경우 5번 노드에 위치하고 있다
그 이유로는 start, end, node, idx가 있을 경우 재귀함수를 통해 트리 생성이 가능하다

int mid = (start + end) / 2
update(start, mid, node x 2, idx); // 왼쪽 자식 노드로 가는 코드
update(mid + 1, end, node x 2 + 1, idx); // 오른쪽 자식 노드로 가는 코드
tree[node] = tree[node x 2] + tree[node x 2 + 1];

이후 B열 기계의 3번을(5번노드) Check을 해준다 (+1을 해줌으로써 케이블이 몇개 겹치는지 계산 가능)

그리고 A열의 두 번째 같은 경우 처음으로 겹치는 케이블이 생기는데

이렇게 sum함수의 경우 (node, start, end, left, right)를 통해
left와 right는 고정되어 있고 (왜냐면 B열을 기준으로 오른쪽에 위치한 것중에 이미 참석한 걸 체크하기에)
start와 end를 계속 줄이며 오른쪽에 있는 B열 배열들 중에 이미 케이블이 있는 경우를 찾고 return해주면 된다

이렇게 계속 진행한다

그리고 한번에 두개가 겹치는 A열의 4번째 같은 경우에는

첫 번째는 예제에 나온 그림과 같이 B열의 3번째 부분에서 +1를 얻을 수 있다

그리고 두 번째는 위와같이 B열의 4번째로부터 +1를 얻을 수 있다
참고로 7번 노드 같은 경우엔 리프 노드지만 아직 방문하지 않았기에 패스한다

A열의 5번은 B열의 5번 즉 끝번이기에 오른쪽에 더이상 없음 -> 겹치는거 X
만약 B열의 다른번(만약 3번)이였으면 옆에 4, 5번이 있기에 겹침

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 500000;

int N;
int arrA[MAX_N + 1], arrB[MAX_N * 2];
long long tree[4 * (MAX_N + 1)];

long long sum(int node, int start, int end, int left, int right){
    if(left > end || right < start) return 0;
    if(left <= start && end <= right) {
    	return tree[node];
	}
    int mid = (start + end)/2;
    return sum(node*2, start, mid, left, right) + sum(node*2 + 1, mid + 1, end, left, right);
}

void update(int node, int start, int end, int idx) {
	if (idx < start || end < idx) return;
    if (start == end) {
        tree[node]++;
        return;
    }
    
	int mid = (start + end)/2; 
	update(node * 2, start, mid, idx); // 왼쪽 자식 노드로 
	update(node * 2 + 1, mid + 1, end, idx); // 오른쪽 자식 노드로
	 tree[node] = tree[node * 2] + tree[node * 2 + 1];
	 
}

int main() {
	
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); cout.tie(NULL);
	
	
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arrA[i];
    }
    for (int i = 1; i <= N; i++) {
        int num;
        cin >> num;
        arrB[num] = i;
    }
    
    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += sum(1, 1, N, arrB[arrA[i]] + 1, N); // node, start, end, left, right
        update(1, 1, N, arrB[arrA[i]]); // node, start, end, idx
    }
    cout << ans;
    return 0;
}