ABC212 D Querying Multiset
問題文がややこしいので, 操作を一旦整理すると次のようになる.
操作1: 袋に整数$ X_iを入れる.
操作2: 袋に入っている整数すべてに$ X_iを加算する.
操作3: 袋に入っている整数のうち最小の物を出力し, 袋から取り出す.
ここで, 袋の具体的な実装としてmultisetを用意する. multisetでは整数の挿入, 先端の要素の削除を要素数を$ Nとして$ O(\log N)で実現できる. しかし, 操作2については愚直に行うと$ O(N)かかってしまう. そこでこれを高速化することを考える.
ここで, 今まで加算された$ X_iの総和を$ Sとおく. すると, 操作1を行う際入れる整数$ X_iから$ Sを引き, 操作3を行う際は出力する整数に$ Sを加算することによってすべての要素を調べて加算する必要がなくなり, 高速化される.
よって, $ O(Q \log Q)でこの問題を解くことができた.