import sys
input = sys.stdin.readline
M = 1<<21
def updatefenwick(i,v):
while i<=M:
fenwick[i] += v
i += i&-i
def find(x,i,c):
if fenwick[i] >= x and fenwick[i]-data[i] < x:
return i
if fenwick[i] >= x:
return find(x,i-2**c,c-1)
return find(x-fenwick[i],i+2**c,c-1)
data,fenwick = [0]*(M+1),[0]*(M+1)
for _ in range(int(input())):
t,x = map(int,input().split())
if t == 1:
updatefenwick(x,1)
data[x] += 1
else:
idx = find(x,M,20)
data[idx] -= 1
updatefenwick(idx,-1)
print(idx)
이분탐색과 팬윅트리로 해결하였다.
사탕상자 [백준 2243번] 사탕상자 (Python3) (tistory.com) 와 사실상 똑같은 문제이다. 쿼리의 개수가 더 많아서 시간제한이 빡세긴 하지만 알고리즘적으로 차이점은 없다.