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
N = int(input()); M = 1<<19
data = sorted([(int(input()),i) for i in range(1,N+1)],reverse=True)
fen = [0]*(M+1); result = [0]*N
for x,i in data:
result[i-1] = sumfen(i-1)+1
updatefen(i)
print(*result,sep="\n")팬윅트리로 해결하였다.
세그먼트 트리 유형의 문제라는 것은 알고 있었는데, 풀이가 쉽게 떠오르지 않는 문제였다. 그래서 나중에 풀기 위해 남겨뒀었다. 그러다가 순열 [백준 1849번] 순열 (Python3) (tistory.com) 문제를 풀고나자 풀이가 생각이 났다.
입력값을 특정 순서대로 팬윅트리에 넣고, 변화하는 구간합을 문제에 이용하는 것이 포인트였다.
풀이를 설명하면,
1. 달리고 있는 선수들의 실력을 기준으로 순서대로 정렬한다.
2. 가장 실력이 좋은 선수부터 차례대로 현재 달리고 있는 위치에 팬윅트리에 +1 해준다.
3. 현재 달리고 있는 위치 앞쪽에 현재까지 몇 명이 있는지의 구간합을 구하고, 그 값보다 1 큰 값이 곧 등수이다.
내 앞쪽에 달리고 있는 나보다 실력이 좋은 선수의 수+1이 곧 등수이다. 따라서 실력이 좋은 순서대로 팬윅트리 혹은 세그먼트 트리를 갱신하는것이 핵심이다.
오늘의 교훈) 다양한 세그먼트 트리 (팬윅트리) 응용문제를 풀어보자