実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 180

問題概要

空の袋に対して $Q$ 個のクエリが与えられるので順に処理せよ。なお、クエリには次の3種類がある。

クエリ :
- 1 x : 整数 $x$ が書かれたボールを1個袋に入れる。
- 2 x : 整数 $x$ が書かれたボールを1個袋から取り出す。ただし、このクエリが与えられるとき、袋の中に整数 $x$ が書かれたボールが存在することが保証される。
- 3 : 袋の中のボールの種類数を出力する。

制約

入力はすべて整数。
$1 \leq Q \leq 2 \times 10^5$
$1 \leq x \leq 10^6$

考察

クエリの形式から、ボールの種類とそれに対応する個数を記録していけばよいことが分かる。このようなときは前者をkey、後者をvalueとした連想配列 (C++ ではmapやunordered_map) を用いると便利である。

クエリ2についてはvalueが0になったkeyを削除しないと、クエリ3で出力する連想配列のサイズが変わってしまうので注意しよう。

コード

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

// ======================================== //

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

    unordered_map<int, int> mp;
    while (Q--)
    {
        int t, x;
        cin >> t;

        if (t == 1)
        {
            cin >> x;
            mp[x]++;
        }
        else if (t == 2)
        {
            cin >> x;
            mp[x]--;

            if (mp[x] == 0)
                mp.erase(x);
        }
        else if (t == 3)
        {
            cout << mp.size() << endl;
        }
    }
}