Partially Retroactive Priority Queue

概要

普通のPriority Queueが現在の列に対するPush、Popしか行えないのに対して、Retroactive Priority Queueは好きな時刻に操作を追加したり取り消したりできる。
また、Partially Retroactiveは現在の状態のみ、Fully Retroactiveは任意の時刻の状態を取得できる。

操作

constructor(int N): 長さNの「何もしない」で初期化
set_op_push(int k, T x): k番目の操作をPush(x)に変更
set_op_pop(int k): k番目の操作をPopに変更(優先度はcmpで指定)
set_op_null(int k): k番目の操作を「何もしない」に変更
size(): 現在の残っている要素数を返す
empty(): 現在の残っている要素数が0か
top(): 現在残っている中で最も優先度が高い要素を返す
all_prod(): 現在残っている要素を演算opで纏めた値を返す(内部的には追加された時刻の昇順に演算が行われる)

Partially Retroactive Priority Queue

概要

操作

実装

使用例1

使用例2