ABC ではしばしば c++ における multiset/set を要求するような問題が出ますが，python にはそのような機能が備わっていないため，苦労した人も多いかと思います．ここでは multiset を用いない解法を紹介します．

\(S\) に含まれるそれぞれの要素の個数を管理する連想配列 \(\mathrm{cnt}\) および最大値，最小値それぞれを管理する優先度付きキュー \(\mathrm{MAX,MIN}\)を用意します．

• クエリ 1 に対して，\(\mathrm{cnt}[x]\leftarrow \mathrm{cnt}[x]+1\) とします．また，\(\mathrm{MIN,MAX}\) それぞれに \(x\) を追加します．

• クエリ 2 に対して，\(\mathrm{cnt}[x]\leftarrow \max(0,\mathrm{cnt}[x]-c)\) とします．

• クエリ 3 に対して，\(\mathrm{cnt}[\mathrm{MIN}[0]]>0\) となるまで \(\mathrm{MIN}\) を pop し続けます．最大値も同様に処理します．このとき，\(\mathrm{MAX}[0]-\mathrm{MIN}[0]\) が答えです．

計算量は \(O(N \log N)\) です．実装例

また，multiset/set の代用ができるものがウェブ上に公開されているので，いくつか紹介します．これらを駆使することで，想定解が multiset/set を用いるものであっても，Python で解くことができる問題が多くあります．

• 平方分割を用いるもの ( tatyam さん)

• heapq を用いるもの ( Tsubo さん)

• Binary Indexed Tree を用いるもの ( jupy さん)