AtCoder ABC 212 D - Querying Multiset (2Q, 茶色, 400 点)

面白かった。priority queue と、「全体に反映させる値を別にもつ」テクニックを学べる問題。

• 問題へのリンク

問題概要

はじめ、何も入っていない袋がある。次の 回のクエリに答えよ。

• クエリタイプ 1：袋に、 と書かれたボールを入れる
• クエリタイプ 2：袋に入っているすべてのボールに対して、書かれている数を、 を加えた数で書き直す
• クエリタイプ 3：袋から、書かれている数が最小であるボールを取り出して、その値を出力する

制約

• 

考えたこと

もし、クエリタイプ 2 がなければ、単なる「priority queue のシミュレーションを行うだけの問題」である。つまり、次の問題と一緒だ。

atcoder.jp

クエリタイプ 2 を愚直にこなすためには、priority queue に入っているすべてのボールを一度取り出して、 を加えて、priority queue に戻す必要がある。しかし、そんなことをしていたのでは計算に時間がかかってしまう。

そこで、「priority queue の全要素にあとで加える値」を別に管理することにしよう！！

---

• offset：priority queue の全要素にあとで加える値

---

これを持つと、各クエリは次のように処理できる。

クエリタイプ 1（挿入）

値 を挿入するためには、offset の分を差し引いて、値

X - offset

の要素を priority queue に挿入すればよい。

クエリタイプ 2（加算）

offset += X

とすればよい。

クエリタイプ 3（取り出し）

priority queue から、値が最小の要素を取り出す。その値を val として、

val + offset

の値を出力すればよい。

計算量

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long Q, type, X;
    cin >> Q;

    long long offset = 0;
    priority_queue<long long, vector<long long>, greater<long long>> que;
    while (Q--) {
        cin >> type;
        if (type == 1) {
            cin >> X;
            que.push(X - offset);
        } else if (type == 2) {
            cin >> X;
            offset += X;
        } else {
            auto val = que.top();
            que.pop();
            cout << val + offset << endl;
        }
    }
}