ABC 253 C 勉強メモ

コードは公式解説ページの実装例より

TODO

• st.erase の部分をイマイチ理解出来ていないのであとで調べる

コード

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

int main() {
    int q;
    cin >> q;

    // multiset は要素をキーにアクセスできるコンテナ。
    // 小さいものから大きいものにソートされる (Compare, で指定できる)
    // find()  -> キーに一致した要素の最初のイテレータ S[1, 1, 1] なら S[0] のが返る的な
    // count() -> キーに一致した要素の個数

    // c++   イテレータ -> 反復子、++で進む [0, 1, 2, ..., N] で1のイテレータ i -> i++ -> 2 を指す
    // c++ 逆イテレータ -> 反復子、++で戻る [0, 1, 2, ..., N] で1のイテレータ i -> i++ -> 0 を指す
    // イテレータ はポインタのようなもの。*はそれの指す値 (C言語のポインタと同じ)
    multiset<int> st;

    while (q--) {
        int t;  // query type
        cin >> t;

        if (t == 1) {
            int x;
            cin >> x;
            st.insert(x);
        } else if (t == 2) {
            int x, c;
            cin >> x >> c;

            // min(c, xの個数)
            // c が 0になったが x がまだある -> c で打ち止め
            // c は 1以上あるが x がもう無し -> 削除対象がなくなったので打ち止め
            // 多重集合内に要素なし -> 削除できないのでwhile 内を処理しない

            // st.count() の計算量
            // 要素数を N, st に含まれる x の個数を k とすると
            // O(k + logN)
            // -> 2分探索 + カウント を行っていると思われる
            // 以下は 計算量が O(log N) になるための工夫で st.find() を使用している
            while (c-- and st.find(x) != st.end()) {
                // [注意!]
                //    multiset<int> st = {3, 3, 3, 4}; に
                //    普通に st.erase(3) とかすると
                //    { 4 }, になり、3の要素すべてが削除されてしまう。
                //    イテレータへの理解が必要
                st.erase(x);
            }
        } else {
            // rbegin() -> 末尾の逆イテレータ, *つけてるので最大値
            // begin()  -> 先頭の  イテレータ, *つけてるので最小値
            cout << *st.rbegin() - *st.begin() << endl;
        }
    }
}