arc 033 C - データ構造 (python)

これの下位互換。
F - Absolute Minima
abc 127 F - Absolute Minima (python) - aacord’s memo

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1
  
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return memo, len(list2)

q = int(readline())
L = [list(map(int,readline().split())) for i in range(q)]
 
#座圧する
chk = []
for i in range(q):
    if L[i][0] == 1:
        chk.append(L[i][1])
        
memo, len_memo = compress(chk)
memo_inv = dict([(v,k) for k,v in memo.items()])

#値を管理するBIT
bit = Bit(len_memo)
#要素数を管理するBIT
num = Bit(len_memo)
  
for i in range(q):
  que = L[i]
  if que[0] == 1:
    a,b = que
    bit.add(memo[b]+1,b)
    num.add(memo[b]+1,1)
  else:
    d = num.lower_bound(que[1])
    m = memo_inv[d-1]
    print(m)
    bit.add(d,-m)
    num.add(d,-1)