[백준] 7578 - 공장 (Python)

---

케이블이 교차하기 위한 조건은 무엇일까?. A열 기계를 모두 배치한 상황에서 B열 기계를 하나씩 배치하는 상황을 가정하겠다.

n번째 B열 기계와 연결되는 A열 기계의 위치(인덱스)를 $loc[n]$ 라고 하자. 기존에 배치된 기계 m에 대해서 $loc[n] < loc[m]$ 을 만족한다면 교차하게 된다.

그렇다면 n번째 기계를 배치할 때 생기는 교차점의 수는 기존에 배치된 기계 중 인덱스가 $loc[n]$ 보다 큰 것의 개수와 같다.

$loc[n]$보다 큰 구간 내에 존재하는 모든 값을 빠르게 구하기 위해 배치된 기계의 수를 저장하는 세그먼트 트리를 사용한다.

---

import sys
input = sys.stdin.readline

# 세그먼트 트리의 구성과 동시에 교차점의 개수를 구함
def locate(left, right, node, idx):
    seg_tree[node] += 1
    if left == right:
        return 0
    mid = (left+right) // 2 
    # idx보다 오른쪽에 있는 구간의 합을 구함
    if idx <= mid:
        return locate(left, mid, node*2, idx) + seg_tree[node*2+1]
    else:
        return locate(mid+1, right, node*2+1, idx)
        
n = int(input())
seg_tree = [0]*(4*n)
# loc는 A열에 배치된 기계번호의 인덱스
loc = {}
count = 0
for i, a in enumerate(map(int, input().rstrip().split())):
	# 1부터 n까지의 값을 사용한다
    loc[a] = i+1
    
for b in map(int, input().rstrip().split()):
    count += locate(1, n, 1, loc[b])
    
print(count)

---

더 효율적으로 생각해보자. 인덱스의 오른쪽에 있는 값을 구하는 것이므로 구간 합으로도 가능하지만 누적 합으로도 구현이 가능하다.

누적 합을 빠르게 구해주고 더 작은 공간을 사용하는 펜윅 트리를 사용해 보자.

---

import sys
input = sys.stdin.readline

# m은 트리 전체 구간의 합
def locate(m, idx):
	# 왼쪽 구간의 누적합
    acc_num = 0
    k = idx
    # 누적합을 구함
    while k > 0:
        acc_num += fenwick_tree[k]
        k -= k & -k 

    k = idx
    # 트리에 삽입
    while k <= n:
        fenwick_tree[k] += 1 
        k += k & -k 
    # 오른쪽 구간의 누적합을 리턴
    return m - acc_num
    
n = int(input())
fenwick_tree = [0]*(n+1)
loc = {}
count = 0
for i, a in enumerate(map(int, input().rstrip().split())):
    loc[a] = i+1
    
for i, b in enumerate(map(int, input().rstrip().split())):
    count += locate(i, loc[b])
    
print(count)