The queries in the Problem Statement can be processed fast with, for example, std::multiset in C++.

Sample code:

#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;
        }
    }
}

There are several noteworthy points on std::multiset, which is used for solving this problem. We will introduce them as well as the resolutions.

Suppose that we have declared:

std::multiset<int> st;

1. Behavior of erase()

What will happen if you do

st.erase(3)

when st contains \(\{3,3,4\}\)? We’d be happy if only one \(3\) is removed, but actually the contents of st turns out to be \(\{4\}\). If you pass a value as the argument of erase(), it will erase all the elements with that value, so you should be careful.

If you want to erase single \(x\), you should write as follows instead.

st.erase(st.find(x))

2. The complexity of count()

st.count(x) costs \(\mathrm{Ο}(k+\log N)\) computation time, where \(N\) is the number of elements in st and \(k\) is the number of \(x\)’s contained in st.

Thus, if you use st.count(x) when processing query 2, it will cost a total of \(\mathrm{Ο}(Q^2)\) time at worst. Instead, you shuold use \(\mathrm{Ο}(\log N)\), which costs \(\mathrm{Ο}(\log N)\) time. Since st.find(x) is called at most \(\mathrm{Ο}(Q)\) times, it will now fit the time limit.