[백준 7578번] 공장 (Python3)

def update(i):
  while i<M:
    fen[i] += 1
    i += i&-i

def SUM(i):
  S = 0
  while i:
    S += fen[i]
    i -= i&-i
  return S

N = int(input()); M = 1<<19

D1,D2 = [[*map(int,input().split())] for i in range(2)]
Index = [0]*(1<<20)
for i in range(N):
  Index[D1[i]] = i+1

fen = [0]*M
result = 0

for i in range(1,N+1):
  idx = Index[D2[-i]]
  result += SUM(idx)
  update(idx)
print(result)

팬윅트리로 해결하였다.

 

처음에 접했을때는 아이디어를 떠올리기 힘든 문제였는데, 달리기 [백준 2517번] 달리기 (Python3) (tistory.com), Counting Inversions [백준 10090번] Counting Inversions (Python3) (tistory.com) 를 풀고 나니 표현만 달라진 똑같은 문제라는 사실을 알게되었다.

 

 

여담) 내 풀이가 파이썬 기준 성능 1위를 기록했다.