問題の概要

この問題は「優先度付きキュー（ヒープ）」とよばれるデータ構造の練習問題です。例えば Python では heapq として、 C++ では priority_queue として、実装されています。

---

注意：最大・最小ヒープについて

Python の heapq はデフォルトで「最小値」を保持する最小ヒープ であるのに対して、 C++ の priority_queue はデフォルトで「最大値」を保持する最大ヒープとして動作します。

そのため、（今回の問題のように） C++ で最小値を優先して取り出すには、変数の宣言時に以下のように型引数を追加する必要があります。

priority_queue<int, vector<int>, greater<int>> que;

---

ヒープにできること

実装方針によって、細かなメソッド・計算量は異なりますが、およそ以下のような操作ができます。以下、操作時のヒープの要素数を \(N\) とします。

1. 最小値の取得

• （削除はせず）ヒープ内の最小値を取得します
• 計算量 \(O(1)\)
• Python : que[0]
• C++ : que.top()

2. 最小値の取り出し

• ヒープ内の最小値を削除します
• 計算量 \(O(\log N)\)
• Python : heappop(que)
• C++ : que.pop()

3. 要素の追加

• ヒープに要素を追加します
• 計算量 \(O(\log N)\)
• Python : heappush(que, x)
• C++ : que.push(x)

---

実装

今回の問題であれば

• タイプ \(1\)

  ヒープに \(h\) を追加する。

• タイプ \(2\)

  最小値を取得し、それが \(h\) 以下なら削除する。\(h\) 以下でなくなるまで繰り返す。

というようなシミュレーションを書くことで、この問題に AC できます。以下のように実装できます。

Python での実装

from heapq import heappop, heappush

que = []
q = int(input())
for i in range(q):
    t, h = map(int, input().split())
    if t == 1:
        heappush(que, h)
    else:
        while que and que[0] <= h:
            heappop(que)
    print(len(que))

C++ での実装

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

int main(){
    int q; cin >> q;
    priority_queue<int, vector<int>, greater<int>> que;
    for(int i=0; i<q; i++){
        int t, h; cin >> t >> h;
        if (t == 1){
            que.push(h);
        }else{
            while(!que.empty() and que.top() <= h){
                que.pop();
            }
        }
        cout << que.size() << endl;
    }
}

---

計算量

計算量については以下のようになります。

• 挿入

  タイプ \(1\) のクエリごとに \(1\) 回行います。よって全体で \(O(Q)\) 回です。

• 削除

  タイプ \(2\) では \(1\) 回のクエリで、たくさんの要素を削除することもあり、計算量が大きくなると感じるかもしれません。

  しかし、一度削除した要素は二度と削除できないことをかんがえると、「削除の回数」は「挿入の回数」以下となるはずです。よって全体で \(O(Q)\) 回です。

• 最小値の取得

  ほとんど削除回数と同じです。タイプ \(2\) のクエリで、「最小値を確認したが、削除しない要素」が存在することがあります。

  しかし、それは \(1\) クエリにつき高々 \(1\) つしか存在しないため、削除回数より高々 \(Q\) 回しか大きくなりません。よって全体で \(O(Q)\) 回です。

以上をまとめると、計算量は \(O(Q \log Q)\) となります。