atcoder ABC212 D - Querying Multisetの勉強

クエリ atcoder

atcoder.jp

・参考
Querying Multiset [AtCoder Beginner Contest 212 D] - はまやんはまやんはまやん

・説明
　優先度付きキューのheapqを使う。操作2では全体に足されている値をoffsetで管理する。
　heapq.heappushするときにXiでなくXi-offsetを加えることに注意。例えばoffset=2, キューが[2, 1, 6]のとき、9をそのまま加えると[2, 1, 6, 9]になるが本来全体に+offsetして[4, 3, 8, 9]になるべきなので[2, 1, 6, 7]と7を加える。

import heapq
h=[]
heapq.heapify(h)

q=int(input())
offset=0

for i in range(q):
  l=list(map(int,input().split()))
  
  if l[0]==1:
    heapq.heappush(h,l[1]-offset)

  if l[0]==2:
    offset+=l[1]
    
  if l[0]==3:
    print(heapq.heappop(h)+offset)