ABC253C - Max - Min Query - 競プロはじめました

解法1：順序付き集合（c++）
解法2：heapq（Python）
- 考え方
- 回答例

解法1：順序付き集合（c++）

考え方

辞書で個数を管理して，順序付集合でmax, minを算出すればよい．

回答例（setとmap）

mapはPythonのdefaultdictと同じように使える（PythonでC++のstd::mapみたいな挙動が欲しい | Akashic Records）
setはソートされている．maxの要素を指すイテレータはendではなくrbegin．

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

int main() {
  int Q;
  cin >> Q;
  map<int, int> m;
  set<int> s;
  for (int i = 0; i < Q; i++) {
    int j, x, c;
    cin >> j;
    if (j == 1) {
      cin >> x;
      s.insert(x);
      m[x]++;
    } else if (j == 2) {
      cin >> x >> c;
      m[x] -= min(c, m[x]);
      if (m[x] == 0) {
        s.erase(x);
      }
    } else {
      cout << *s.rbegin() - *s.begin() << endl;
    }
  }
  return 0;
}

回答例（multiset）

「setとmap」ではなく「multiset」を使う．erase()やfind()の使い方に気をつける必要がある．
Editorial - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

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

int main() {
  int Q;
  cin >> Q;
  multiset<int> s;
  for (int i = 0; i < Q; i++) {
    int j, x, c;
    cin >> j;
    if (j == 1) {
      cin >> x;
      s.insert(x);
    } else if (j == 2) {
      cin >> x >> c;
      while (c > 0 and s.find(x) != s.end()) {
      	s.erase(s.find(x));
        c--;
      }
    } else {
      cout << *s.rbegin() - *s.begin() << endl;
    }
  }
  return 0;
}

解法2：heapq（Python）

考え方

defaultdictで要素数を管理する．

max, minは

要素数が0→1になったとき
要素数が0になったとき

に変化し得る．最初の方は簡単に処理できるが，もう一方をどう処理するかが問題．昇順に要素を取り出すのはheapqでできる．降順に取り出すのは要素の符号を反転させれば，これもheapqでできる．

また，クエリ全体で追加・削除する回数は$O(Q)$しかないことに注意．

回答例

heapqにはすでになくなった要素も含まれるので，要素が存在するかどうかをsetで管理する．

from collections import defaultdict
from heapq import heappush, heappop

Q = int(input())

d = defaultdict(int)
s = set()
q_max = []
q_min = []
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        x = q[1]
        d[x] += 1
        if x not in s:
            s.add(x)
            heappush(q_max, -x)
            heappush(q_min, x)
    elif q[0] == 2:
        x, c = q[1:]
        d[x] -= min(c, d[x])
        if d[x] == 0 and x in s:
            s.remove(x)
    else:
        while - q_max[0] not in s:
            heappop(q_max)
        while q_min[0] not in s:
            heappop(q_min)
        print( - q_max[0] - q_min[0])