[백준 12899번] 데이터 구조 (Python3)

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) 와 사실상 똑같은 문제이다. 쿼리의 개수가 더 많아서 시간제한이 빡세긴 하지만 알고리즘적으로 차이점은 없다.