LG#P3378. 【模板】堆

【模板】堆

P3378 【模板】堆

题目描述

\hspace{15pt}给定一个初始为空的数列,请支持以下三种操作:

1. {\hspace{20pt}}_\texttt{1.}\,给定一个整数 xx,将 xx 加入数列中;

2. {\hspace{20pt}}_\texttt{2.}\,输出数列中最小的数;

3. {\hspace{20pt}}_\texttt{3.}\,删除数列中最小的数。如果有多个数都是最小的,只删除其中的一个。

\hspace{15pt}一共要进行 nn 次操作,请你按照输入给出的顺序依次执行这些操作,并对每一次操作 22 给出回答。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦106)n \left(1 \leqq n \leqq 10^6\right) 代表操作的次数。

\hspace{15pt}此后 nn 行,第 ii 行输入一次操作,每行先输入一个整数 op(1≦op≦3)op \left(1 \leqq op \leqq 3\right) 代表操作类型,编号同题干:

∙ \hspace{23pt}\bullet\,若 op=1op=1,紧接着在同一行输入一个整数 x(1≦x<231)x \left(1 \leqq x < 2^{31}\right) 代表要加入数列的数;

∙ \hspace{23pt}\bullet\,若 op=2op=2,该行只有 opop 一个整数;

∙ \hspace{23pt}\bullet\,若 op=3op=3,该行只有 opop 一个整数。

\hspace{15pt}保证当 op=2op=2 或 op=3op=3 时,数列不为空。

输出格式

\hspace{15pt}对于每一次 op=2op=2 的操作,新起一行输出一个整数,代表当时数列中最小的数。

测试样例

5
1 2
1 5
2
3
2
2
5

样例 1 解释

\hspace{15pt}依次执行 55 次操作,数列的变化如下:

∙ \hspace{23pt}\bullet\,操作 11(x=2x=2):数列变为 {2}\{2\};

∙ \hspace{23pt}\bullet\,操作 11(x=5x=5):数列变为 {2,5}\{2,5\};

∙ \hspace{23pt}\bullet\,操作 22:数列中最小的数是 22,输出 22;

∙ \hspace{23pt}\bullet\,操作 33:删除数列中最小的数 22,数列变为 {5}\{5\};

∙ \hspace{23pt}\bullet\,操作 22:数列中最小的数是 55,输出 55。

\hspace{15pt}因此依次输出 22 和 55。

8
1 4
1 2
2
1 6
3
2
3
2
2
4
6

提示

\hspace{15pt}对于 30%30\% 的数据,n≦15n \leqq 15;

\hspace{15pt}对于 70%70\% 的数据,n≦104n \leqq 10^4;

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1061 \leqq n \leqq 10^6,1≦x<2311 \leqq x < 2^{31},op∈{1,2,3}op \in \{1,2,3\}。