Contest Duration: - (local time) (100 minutes) Back to Home
Official

## D - Sequence Query Editorial by en_translator

##### 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)$$.

posted:
last update: