2 つの解法を紹介します。

解法 1 (std::set を使う解法)

1 つ目は std::set のような順序付き集合型を利用する方法です。 具体的には、次の手順で「受付に呼ばれたが、まだ受付に行っていない人」の集合を管理しながらイベントを処理していきます。

• called を 「受付に呼ばれたが、まだ受付に行っていない人」の集合とする。はじめ called は空である。
• また、last を最後に呼ばれた人の番号とする。便宜上 はじめ last は \(0\) とする。
• その後、イベントを順に処理する。イベントの種類に応じて次の処理を行う。
  • 1 種類目のイベントの場合、次に呼ばれるのは last + 1 である。よって last に 1 を足したあとに called に last を追加する。
  • 2 種類目のイベントの場合、x を called から削除する。
  • 3 種類目のイベントの場合、called の最小の要素が答えである。よってこれを出力する。

上記の手順中、called に関する操作は「要素の追加」「要素の削除」「最小の要素の出力」です。called の実装に配列や list などを用いると、最悪ケースで時間計算量が \(\mathrm{O}(N^2)\) かかり TLE してしまいますが、std::set のような順序付き集合型を用いることで操作をすべて 1 回あたり \(\mathrm{O}(\log N)\) で行うことができるので、クエリ全体で \(\mathrm{O}(Q \log N)\) でこの問題を解くことができます。

• 実装例 (C++, \(\mathrm{O}(Q \log N)\) )

#include <iomanip>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;

  set<int> called;
  int last = 0;
  while (Q--) {
    int event;
    cin >> event;
    if (event == 1) {
      called.insert(++last);
    } else if (event == 2) {
      int x;
      cin >> x;
      called.erase(x);
    } else {
      cout << *begin(called) << "\n";
    }
  }
}

解法 2 (線形時間で解く方法)

より計算量の良い解法として、時間計算量が \(\mathrm{O}(N + Q)\) である解法も紹介します。

問題の制約から、3 種類目のイベントで呼ばれる番号は広義単調増加するという性質を持ちます。

• 証明：背理法で考えます。3 種類目のイベントで人 \(y\) が呼ばれて、その後 人 \(x\) \((x < y)\) が呼ばれたとします。すると、\(y\) が呼ばれた時点で、人 \(x\) はすでに 1 回以上受付に呼ばれていて(1 回目の呼び出しは番号順であるため) かつ まだ受付に行っていないため、矛盾が発生します。

よって、次のような手順で線形時間で解くアルゴリズムを構成できます。まず、最後に 3 種類目のイベントで読んだ人の番号を変数 ans で常に保持しておきます。そして、3 種類目のイベントが来るたびに、ans の示す人が受付に行っていない人になるまで ans の値をインクリメントして、得られる ans の値を出力します。
この操作によって ans のインクリメントされる回数は \(\min(N, Q)\) 回で抑えられるので、計算量は \(\mathrm{O}(N+ Q)\) になります。

• 実装例 (C++, \(\mathrm{O}(N + Q)\))

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;
  vector<int> gone(N + 1);
  int ans = 1;
  while (Q--) {
    int event;
    cin >> event;
    if (event == 1) {
      // do nothing
    } else if (event == 2) {
      int x;
      cin >> x;
      gone[x] = 1;
    } else {
      while (gone[ans]) ans++;
      cout << ans << "\n";
    }
  }
}