この問題文中のクエリは、例えば c++ なら std::multiset を用いることにより高速に処理できます。

実装例：

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

int main() {
    int q;
    cin >> q;
    multiset<int> st;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            st.insert(x);
        } else if (t == 2) {
            int x, c;
            cin >> x >> c;
            while (c-- and st.find(x) != st.end()) {
                st.erase(st.find(x));
            }
        } else {
            cout << *st.rbegin() - *st.begin() << endl;
        }
    }
}

この問題を解くために必要なデータ構造、 std::multiset を用いる際には注意すべき点があります。以下ではそれらの注意点と対処法をお伝えしようと思います。

最初に、

std::multiset<int> st;

と宣言しているものとします。

1. erase() の仕様

例えば、st の中身が \(\{3,3,4\}\) のときに、

st.erase(3)

と行うとどうなるでしょうか？ \(3\) が一つだけ消えてくれると嬉しいのですが、実際には st の中身は \(\{4\}\) となります。このように、erase() の引数に値を渡すと、その値を全て削除してしまうため、注意が必要です。

\(x\) を一つだけ消したい場合は、以下のように書く必要があります。

st.erase(st.find(x))

詳しくは、c++ のイテレータについて調べてみてください。

2. count() の計算量

st.count(x) は、st の要素数を \(N\) 、st に含まれる \(x\) の個数を \(k\) とすると、\(\mathrm{Ο}(k+\log N)\) の計算量がかかります。

そのため、今回の問題でクエリ \(2\) を処理する際に st.count(x) を用いると最悪の場合の計算量が \(\mathrm{Ο}(Q^2)\) になってしまいます。そのため、計算量が \(\mathrm{Ο}(\log N)\) である st.find(x) を用いる必要があります。st.find(x) が呼ばれる回数は高々 \(\mathrm{Ο}(Q)\) 回のため、この工夫により実行時間に間に合います。