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를 기준으로 정렬해야하기 때문이다.
오늘의 교훈) 다양한 세그먼트 트리 활용문제를 풀어보자.