[백준 5419번] 북서풍 (Python3)

import sys
input = sys.stdin.readline

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

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

for _ in range(int(input())):
  N = int(input()); M = 1<<17
  
  xlist = []; ylist = []
  for i in range(N):
    x,y = map(int,input().split())
    xlist.append([-x,0]); ylist.append((y,-x,i))
  ylist.sort()
  for i in range(N):
    xlist[ylist[i][2]][1] = i+1
  xlist.sort()
  
  fen = [0]*(M+1); result = 0
  for x,i in xlist:
    result += sumfen(i)
    updatefen(i)
  
  print(result)

팬윅트리로 해결하였다.

처음 문제를 봤을 때 풀이가 떠오르지 않았던 문제였다. 그래서 일단 남겨놨던 문제였다.

그러다가 달리기 [백준 2517번] 달리기 (Python3) (tistory.com) 문제를 풀고나자 "어 맞다 그때 그 문제도 이거랑 비슷한데?" 하는 생각에 바로 풀이를 시도해보았다.

달리기 문제보다 약간 더 까다로운 포인트가 있긴 하지만, 거의 유사한 문제이다.

 

풀이를 설명하면,

1. x값과 y값을 정렬하여 값을 압축한다. (압축하지 않으면 x,y값이 10^9까지 가게 된다)

2. 달리기 문제에서와 x값이 작은 순서대로 y값의 위치의 팬윅트리에 +1만큼 갱신하고, 현재 y좌표보다 y값이 작은 값의 합을 팬윅트리의 구간합으로 계산한다.

3. 구간합의 총 합이 곧 섬의 쌍의 수이다.

 

주의해야 할 점은, 값을 압축할 때, 그냥 y값에 대해서 정렬하지 말고 (y,x)꼴의 튜플로 정렬해주어야 한다. y값이 같은 경우에는 x를 기준으로 정렬해야하기 때문이다.

 

 

오늘의 교훈) 다양한 세그먼트 트리 활용문제를 풀어보자.