[백준 17131번] 여우가 정보섬에 올라온 이유 (Python3)

import sys
input = sys.stdin.readline

def update(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

N = int(input()); M = 1<<19
co = [[] for i in range(M)]
for _ in range(N):
  x,y = map(int,input().split())
  co[-y+(1<<18)].append(x+(1<<18))

result = 0; fen = [0]*(M+1)
for y in range(M):
  for x in co[y]:
    result += sumfen(x-1)*(sumfen(M)-sumfen(x))
    result %= 10**9+7
  for x in co[y]:
    update(x)
print(result)

팬윅트리로 해결하였다.

북서풍 [백준 5419번] 북서풍 (Python3) (tistory.com) 문제와 거의 비슷한 문제이다. y좌표를 기준으로 정렬한 후, 팬윅트리를 이용하여 왼쪽 오른쪽의 별의 개수를 구하면 된다.

 

풀이를 설명하면,

1. 400000 크기 이상의 배열을 만든다. (나는 편의를 위해서 2^19 크기로 만들었다)

2. 각 좌표에 대해서 해당하는 y좌표 인덱스의 리스트에 x좌표를 저장한다.

3. y좌표가 큰 순서대로 현재 x 위치에서 좌, 우에 있는 별들의 개수의 곱의 합을 구한다.

4. 현재 y좌표에서의 계산이 끝나면 각각 해당하는 x 위치에 팬윅트리를 갱신한다.

 

1번에서 40만 이상의 배열을 만드는 이유는 좌표의 입력값의 범위가 -20만 ~ 20만이기 때문에 이를 편의를 위해 양수로 취급하기 위해서이다.

2~4번에서 북서풍 문제와 다르게 정렬한 뒤 순서대로 하는 것이 아니라 굳이 y좌표에 대해서 x좌표를 저장했다가 순서대로 하는 이유는 좌표가 같은 경우를 고려해주어야 하기 때문이다. y좌표가 같은 경우에는 별자리를 이루지 않기 때문에 현재 y좌표에 대해서 계산을 끝내놓고 팬윅트리를 갱신해야 한다.

 

 

 

여담으로 내 풀이가 숏코딩 순위 전체 1위, 성능 순위 파이썬 기준 1위가 되었다.