Querying Multiset [AtCoder Beginner Contest 212 D]

https://atcoder.jp/contests/abc212/tasks/abc212_d

前提知識

• priority_queueなど

解説

https://atcoder.jp/contests/abc212/submissions/24696926

今回の問題は、以下のような条件を持つデータ構造を使える、持っていることが解くために必要なこととなる。

• 高速に要素を入れることができる
• 高速に既に入っている最小値の要素を参照して、かつ、取り出すことができる

これを満たすデータ構造として優先度付きキューがあり、自分の実装もそれを使っている。

問題にどう立ち向かうか

「全体に何かする」という問題は割と出るクエリ問題であり、その場合にoffset的なものを使って高速化する
というのは頻出方針である。
この方針をいかに早く出せるかがキーとなる。
自分は多く見てきたので、この発想をすぐに出せた。

offsetを管理しながら解いていく

offsetのひらめきが一番難しいと思うが、そこはクリアしているものとして以下説明していく。
以下のようなデータを保持しながらクエリをさばいていく

• 最小値が先頭に来るような優先度付きキュー que
• キューに入っている要素に足される数 offset

offsetの立ち位置がよくわからないかもしれないが、例えばque = {2,4,9}が入っていて、offset=10となっているならば、
これはキューに実質{12, 14, 19}が入っているものとして考えるということである。
このようにoffsetを定義することで、2番目のクエリが高速に処理できる。

クエリ操作

クエリ1

数の追加なので、queにXを入れればいいが、キューの中身は実質+offsetになっていることになる。
よって、そのまま入れるとX+offsetが入っていることになってしまうので、X-offsetを入れることで、
Xが入っているようにする。

クエリ2

全体に数を足すので、これは丁度offsetに数を足せばいい。

クエリ3

queから最小の要素を取り出してくればいい。
取り出すときに+offsetするのを忘れずに。

今回はあまりに自明すぎて、気にならないかもしれないが、+offsetという制約が入っているせいで
大小関係が変化しないかという部分も考慮しておく必要がある。
今回は変化しないので、問題ない。

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> Q;

    ll offset = 0;
    min_priority_queue<ll> que;

    rep(_, 0, Q) {
        int T; cin >> T;
        
        if (T == 1) {
            ll X; cin >> X;
            que.push(X - offset);
        }
        else if (T == 2) {
            ll X; cin >> X;
            offset += X;
        }
        else {
            ll ans = que.top() + offset;
            que.pop();
            printf("%lld\n", ans);
        }
    }
}