import sys
input = sys.stdin.readline
def updatefenwick(i):
if not i:
return
while i<=M:
fenwick[i] += 1
i += i&-i
def sumfenwick(i):
SUM = 0
while i:
SUM += fenwick[i]
i -= i&-i
return SUM
def find(x,i,c):
x1 = i-sumfenwick(i)
if x>x1:
return find(x,i+2**c,c-1)
if x<x1 or permutation[i-1]:
return find(x,i-2**c,c-1)
return i
N,M = int(input()),1<<17
permutation = [0]*N
fenwick = [0]*(M+1)
for i in range(1,N+1):
idx = find(int(input())+1,M,16)
permutation[idx-1] = i
updatefenwick(idx)
print(*permutation,sep="\n")
팬윅트리 + 이분탐색으로 구현하였다.
사탕상자 [백준 2243번] 사탕상자 (Python3) (tistory.com) 와 비슷한 방법으로 해결할 수 있다. 다만 사탕상자와 비슷한 문제라는 사실을 떠올리기 까다로웠고, 구현도 까다로운 부분이 있었다.
아이디어를 설명하면,
1. 1부터 N까지 각 원소의 값을 입력받을 때, 현재의 숫자가 들어가야하는 위치는, 앞의 비어있는 노드의 개수가 입력값만큼 있는 곳이다. (비어있는 노드에는 현재의 숫자보다 더 큰 값만 들어갈 것이기 때문이다)
2. 위치에 숫자를 넣으면 그 뒤의 위치는 비어있는 노드의 개수가 1씩 줄어든다. 이를 팬윅트리로 구현한다.
3. 비어있는 노드의 개수 = 인덱스값 - 인덱스 앞에 채워져있는 숫자의 개수 = 입력값인 곳을 이분탐색으로 찾는다.
오늘의 교훈) 세그먼트 트리 + 이분탐색에 익숙해지자