On-line solution

Process the queries in order using multiset.
Let \(S\) be a multiset.

• If \(c_i = 1\)
  “Insert” \(x\) to \(S\).

• If \(c_i = 2\)
  Use S.upper_bound(x) to obtain the first iterator greater than \(x\) and decrement the iterator \(k\) times.

• If \(c_i = 3\)
  Use S.lower_bound(x) to obtain the first iterator not less than \(x\) and increment the iterator \((k-1)\) times.

For \(c_i = 2,3\), be careful not to make the iterator go beyond S.begin() and S.end().
The overall time complexity is \(O(N \log N)\).

Off-line solution

Read all the queries firsthand, and do coordinate compression on the values of \(x\).
We denote by \(x'\) the values after coordinate compression. We can use Fenwick Tree or Segtree. (In this editorial, we assume we used Fenwick Tree.)

• If \(c_i = 1\)
  Add \(1\) to \(x'\).

• If \(c_i = 2\)
  Do the binary search for \(m\) on the following problem. > Is the sum for \([m,x']\) greater than or equal to \(k\) on the Fenwick tree? Here, \([a, b]\) denotes a closed segment.

• If \(c_i = 3\)
  Do the binary search for \(m\) on the following problem. > Is the sum for \([x',m]\) greater than or equal to \(k\) on the Fenwick tree?

The overall time complexity is \(O(N \log^2 N)\).
If you use max_right and min_left of ACL (AtCoder Library)’s Segment Tree, the complexity is reduced to \(O(N \log N)\).