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위를 기록했다.