8819: [yosupo] Data Structure - Double-Ended Priority Queue
[Creator : ]
Description
Given a multiset $S=\lbrace S_1, \ldots, S_N \rbrace$. Process the following $Q$ queries in order:
- 0 x: Add $x$ to $S$.
- 1: Output one of the minimum elements in $S$ and remove it from $S$.
- 2: Output one of the maximum elements in $S$ and remove it from $S$.
It is guaranteed that $S$ is not empty when processing queries of types `1` and `2`.
- 0 x: Add $x$ to $S$.
- 1: Output one of the minimum elements in $S$ and remove it from $S$.
- 2: Output one of the maximum elements in $S$ and remove it from $S$.
It is guaranteed that $S$ is not empty when processing queries of types `1` and `2`.
Input
$N\; Q$
$S_1 \cdots S_N$
$\mathrm{Query}_0$
$\vdots$
$\mathrm{Query}_{Q-1}$
$S_1 \cdots S_N$
$\mathrm{Query}_0$
$\vdots$
$\mathrm{Query}_{Q-1}$
Constraints
$0 \leq N \leq 500000$
$1 \leq Q \leq 500000$
$-10^9 \leq S _ i, x \leq 10^9$
$1 \leq Q \leq 500000$
$-10^9 \leq S _ i, x \leq 10^9$
Sample 1 Input
4 10
-3 0 1 3
0 3
2
2
0 -2
0 1
1
1
2
1
2
Sample 1 Output
3
3
-3
-2
1
0
1