各操作 (具体的には \(1\) 種類目および \(2\) 種類目のクエリ) の特徴について考えてみましょう。

両操作ともに操作前と操作後では袋の中に入っている数の種類数は高々 \(1\) つ増えるまたは減ります。ボールを追加する操作については「種類数は \(1\) つ増えるか、種類数が変わらないか」、ボールを取り出す操作については「種類数は \(1\) つ減るか、種類数が変わらないか」であるということです。

この特徴を用いて高速に各操作を行う方法を考えます。各操作において種類数が変わるか変わらないか判定するにはその操作時点である数が書かれたボールが袋の中に何個入っているかわかればよいです。ボールを追加する操作では、すでに袋の中にその数が書かれたボールがある場合は種類数は増えず、そうでない場合は種類数は \(1\) つ増えます。同様にしてボールを取り出す操作についてもある数が書かれたボールの個数がわかれば種類数が減るかを判定できます。

このように、すべてのクエリを処理するのに必要なものは現在の種類数およびある数が書かれたボールが袋の中に何個入っているかの情報です。前者は \(1\) つの整数、後者は 長さ \(10^6\) の整数からなる配列を管理することで実現できます。

詳細は実装例を参照してください。

実装例(C++):

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

int main() {
    int q;
    cin >> q;
    vector<int> cnt(1000000); // cnt[i]=(現時点で (i + 1) が書かれたボールが袋の中に何個あるか//
    int ans = 0; // 現時点での袋の中のボールに書いてある数の種類数
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            x--;
            cnt[x]++;
            if (cnt[x] == 1) ans++; // このときx が書かれたボールが追加された1個のみである
        } else if (t == 2) {
            int x;
            cin >> x;
            x--;
            cnt[x]--;
            if (cnt[x] == 0) ans--; // このとき x が書かれたボールが袋の中にはもうない
        } else {
            cout << ans << "\n";
        }
    }
}

実装例(Python):

q = int(input())
cnt = [0] * 1000000
ans = 0

for _ in range(q):
    t,*x = map(int,input().split())
    if t == 1:
        x[0] -= 1
        cnt[x[0]] += 1
        if cnt[x[0]] == 1:
            ans += 1
    elif t == 2:
        x[0] -= 1
        cnt[x[0]] -= 1
        if cnt[x[0]] == 0:
            ans -= 1
    else:
        print(ans)