[백준] 7578 공장, python

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

 

 

 

 

 

두 기계를 서로 연결했을 때 교차점의 개수를 세는 문제이다.

 

먼저 b의 기계가 a의 몇번째 기계에 해당하는지 기계 식별번호를 인덱스로 변환해 준다.

 

 

 

 

선이 겹치는지를 확인하려면 현재 a에서 b로 연결한 기계 기준 왼쪽에 있는 기계의 인덱스 번호가 크다면 겹치게 된다..

 

여기서 a의 1번째 기계와 연결된 기계는 b의 3번째 기계이다.

그럼 b라인에서 3번째(a의 1번째 기계와 연결)보다 왼쪽에 있는 2번째(a의 4번째 기계와 연결), 1번째(a의 2번째 기계 와 연결) 기계에 연결된 번호가 더 크므로 2개의 선이 겹치게 된다.

 

 

 

 

마찬가지로 a의 3번째 기계는 b의 4번째 기계와 연결되어 있고,

그럼 b에서 4번째 기계 왼쪽의 기계들에서 2번째 기계(a의 3번째 기계와 연결)만 크므로 1개의 선이 겹치게 된다.

 

 

 

따라서 이 문제는 b배열을 왼쪽부터 한 칸씩 진행하며 현재칸 왼쪽에 있는 칸들에 현재칸의 값보다 큰 값이 몇 개 있는지를 세는 문제로 바꿀 수 있다.

 

 

 

세그먼트 트리, python

세그먼트 트리, python

 

 

 

여기서 세그먼트 트리를 사용해서 k값이상의 수의 개수를 O(log(n))으로 구할 수 있다.

 

 

 

기계가 등장했으면 1, 아니면 0을 배열에 저장한다고 가정한다.

k번 이상이 몇 번 등장했는지를 알고 싶으면 등장 횟수를 저장한 배열에서 k+1부터 n-1까지의 구간 합을 구해주면 k값보다 큰 값들의 개수가 된다.

 

 

따라서 기계가 등장했으면 리프노드에 1을 추가하고 세그먼트 트리를 업데이트하고, k+1 ~ n-1 구간합은 세그먼트 트리를 통해 left, right 값을 업데이해 나가면서 구할 수 있다.

 

 

 

 

 

import sys
from collections import defaultdict, deque
from bisect import bisect_left, insort_left
input = sys.stdin.readline

n = int(input())
input_a = list(map(int, input().split()))
input_b = list(map(int, input().split()))

dict = {v:i for i,v in enumerate(input_a)}

a = list(range(n))
b = [dict[x] for x in input_b]

size = 1
while size<n:
    size *= 2

# 기계 등장횟수의 구간합을 저장
segtree = [0] * (size*2)

# 기계가 등장했다면 1추가
def update(value):
    value += size
    while value>0:
        segtree[value] += 1
        value //= 2

# k이상의 숫자를 찾음(등장횟수의 k+1~n-1까지의 합을 구하면됨)
def query(left, right):
    result = 0
    left += size
    right += size
    while left <= right:
        if left % 2 == 1:
            result += segtree[left]
            left += 1
        if right % 2 == 0:
            result += segtree[right]
            right -= 1
        left //= 2
        right //= 2
    return result

answer = 0

for i, value in enumerate(b):
    update(value)
    answer += query(value+1,n-1)

print(answer)