(백준 #7578) 공장(Python3)

by 

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)

Fanwick 트리로 해결했습니다.

처음 접했을 때 아이디어가 떠오르기 어려웠는데 Running(백준 2517호) Running(Python3)(tistory.com), Counting Inversions(백준 10090호) Counting Inversions(Python3 )( tistory.com ), 방금 알아낸 표현은 한 가지 차이점을 제외하고 같은 문제입니다.

여담) 내 솔루션이 파이썬 표준 성능에서 1위를 했다.


'추천 관련글,