【ABC217】E - Sorting Queries - メモ帳がわり

解法

クエリ1とクエリ2だけだった場合、queueを使うだけで解けるのでとても簡単。
ただ、クエリ3が与えられるたびにソートしていると、全体計算量O(N² logN)になって間に合わない。

上記のように、クエリ1とクエリ2はqueueで実現できるので、問題はクエリ3のソートをどうするかという点である。
そこで、挿入時に数の大小によって並び替えられるデータ構造を使うというアイデアが思い浮かぶ。
C++だと、std::setとかstd::priority_queueが使える。
今回はpriority_queueを使うことにする。
priority_queueは、デフォルトだと降順に並び替えられるので昇順に設定し直しておくこと。

具体的には、次のような操作をする。

クエリ1
- queueにxを追加する
クエリ2
- priority_queueが空でない場合、priority_queueから一つ取り出して出力する
- priority_queueが空の場合、queueから一つ取り出して出力する
クエリ3
- queueに入っている数を全て取り出し、priority_queueに入れ替える

priority_queueへの挿入、取り出しはO(logN)であるため、全体でO(NlogN)の計算量になり間に合う。

priority_queueで実装

priority_queueは降順になるようにしておきましょう。

int main(){
    ll Q;
    cin >> Q;
    
    queue<ll> que;
    // 降順にしておくこと
    priority_queue<ll, vector<ll>, greater<ll>> heapq;
    REP (i, Q) {
        ll t;
        cin >> t;
        if (t == 1) { // クエリ1
            ll x;
            cin >> x;
            que.push(x);
        } else if (t == 2) { // クエリ2
            if (!heapq.empty()) {
                c(heapq.top()); // priority_queueで最小の数を出力
                heapq.pop();
            } else {
                c(que.front());
                que.pop();
            }
        } else { // クエリ3
            while (!que.empty()) {
                // priority_queueからqueueに移し替え
                heapq.push(que.front());
                que.pop();
            }
        }
    }

    return 0;
}

multisetで実装

コンテスト本番はmultisetを使って実装しました。
priority_queueを使う方が楽なのは、コンテスト終了後に気付きました。

multisetから要素を削除するときに、値を渡してしまうと同じ値の要素が複数消去されてしまうので注意。
一個だけ消したい時はイテレータを渡します。

↓参照

minus9d.hatenablog.com

この仕様は知っていたのですが1WAしてしまいました。

int main(){
    ll Q;
    cin >> Q;
    
    queue<ll> que;
    multiset<ll> st;
    ll cnt = 0; // multiset内の要素数
    REP (i, Q) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll x;
            cin >> x;
            que.push(x);
        } else if (t == 2) {
            if (cnt) {
                c(*st.begin()); // 一番小さい数を出力
                st.erase(st.begin()); // 一番小さい数を消去
                cnt--;
            } else {
                c(que.front());
                que.pop();
            }
        } else {
            while (!que.empty()) { // 移し替え
                st.insert(que.front());
                que.pop();

                cnt++;
            }
        }
    }

    return 0;
}

感想

コンテスト終了後に気づいたけど、問題タイトルが凄いヒントになってますね。
次からはタイトルも見ておくことにします。