NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）C - Max - Min Query

問題の要約
整数の多重集合Sがある。はじめSは空。
Q個のクエリが与えられるので順に処理せよ。クエリは次の3種類のいずれか。
　・1 x:Sにxを1個追加する。
　・2 x c:Sからxをmin(c,(Sに含まれるxの個数))個削除する。
　・3:(Sの最大値)-(Sの最小値)を出力。このクエリを処理するとき、Sが空でないことが保証される。

制約
1<=Q<=2*10^5
0<=x<=10^9
1<=c<=Q

入力
Q
query1
...
queryQ

考え方
1,問題文に多重集合と書いてあるので、multisetでもよいが、今回はmapで考えてみる。
2,クエリの処理を考える。(map<long long,long long> mpで管理する)
　1の場合、++mp[x]でよい。
　2の場合、min(c,(Sに含まれるxの個数))をmin_numとすると、mp[x]-=min_numでよい。
　3の場合、mp.rbegin()->first-mp.begin()->firstではだめ。
　　　　　なぜならmp.rbegin()->second,mp.begin()->secondともに0である可能性がある。
　　　　　よって、0のものは無視する。

実際のプログラム
#include<iostream>
#include<map>

using namespace std;

int main(){
  int Q;
  cin >> Q;
  
  map<long long, long long> mp;
  for(int i = 0; i < Q; ++i){
    int q;
    long long x,c;
    cin >> q;
    if(q == 1){
      cin >> x;
      ++mp[x];
    }else if(q == 2){
      cin >> x >> c;
      long long min_num = min(c,mp[x]);
      mp[x] -= min_num;
    }else if(q == 3){
      auto it_r = mp.rbegin();
      while(it_r->second == 0){
        ++it_r;
      }
      
      auto it = mp.begin();
      while(it->second == 0){
        ++it;
      }
      cout << it_r->first - it->first << endl;
    }
  }
  
  return 0;
}