クエリを先読みしない方法について

multiset を用いて、クエリを順番に処理していきます。
multiset を \(S\) とします。

• \(c_i = 1\) のとき
  \(S\) に \(x\) を挿入( insert )すればよいです。

• \(c_i = 2\) のとき
  S.upper_bound(x) によって \(x\) より大きい最初のイテレータを取得し、イテレータを \(k\) 回デクリメントすればよいです。

• \(c_i = 3\) のとき
  S.lower_bound(x) によって \(x\) より小さくない最初のイテレータを取得し、イテレータを \(k-1\) 回インクリメントすればよいです。

\(c_i = 2,3\) において、イテレータが S.begin() や S.end() を超えないように注意して実装しましょう。
全体の計算量は \(O(N \log N)\) です。

クエリを先読みする方法について

クエリを先読みして、\(x\) の値について座標圧縮しておきます。
以下、座標圧縮後の値を \(x'\) で表します。
Fenwick Tree または Segtree を用います。(以下解説ではFenwick Treeを用いたとします。)

• \(c_i = 1\) のとき
  \(x'\) に \(1\) 加算すればよいです。

• \(c_i = 2\) のとき

  Fenwick Tree において \([m,x']\) の和が \(k\) 以上か？

  という問題において、\(m\) について二分探索すればよいです。
  なお、記号 \([a,b]\) は閉区間を意味しています。

• \(c_i = 3\) のとき

  Fenwick Tree において \([x',m]\) の和が \(k\) 以上か？

  という問題において、\(m\) について二分探索すればよいです。

上記を素直に実装すると、全体の計算量は \(O(N \log^2 N)\) になります。
ACL の Segtree の max_right や min_left 関数を用いて \(O(N \log N)\) にすることもできます。