Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 253 C問題 Max - Min Query

AtCoder ABC ABC253 C問題 300 pts

問題

提出解答

(ヒープ) atcoder.jp

問題の概要

多重集合 $S$ がある. 最初, $S$ は空集合である. 次の $Q$ 個のクエリを順に処理せよ.

Type 1: $S$ に $x$ を $1$ 個追加する.
Type 2: $S$ から $x$ を $\min(c, \chi_S(x))$ 個削除する. ただし, $\chi_S(x)$ は $S$ にある $x$ の個数.
Type 3: $\max S- \min S$ を出力する.

制約

$1 \leq Q \leq 2 \times 10^5$
$0 \leq x \leq 10^9$
$1 \leq c \leq Q$
Type 3 のクエリ処理時, $S$ は空集合ではない.

解法

この問題に必要な操作は

挿入
個数を求める.
削除
最大値, 最小値の発見

である. C++ では multiset で全て高速に実現できる.

しかし, Python においてはこれらを高速に処理できるようなデータ構造がデフォルトで用意されていない. よって, 以下のうちのどれかで対処しなければならない.

上記の操作を高速に処理できるようなデータ構造を自作する.
クエリを $\sqrt{Q}$ 個ずつのブロックに分割する.
ヒープを利用する.
BIT 木を使う.

なおこの記述は atcoder.jp を参考にした.

例えば, ヒープを利用したデータ構造は挿入と削除に $O(\log N)$ , 最大値, 最小値の取得と個数の取得は $O(1)$ で処理できる.