#ABC217E. 排序与询问

排序与询问

AT_abc217_e [ABC217E] Sorting Queries

题目描述

\hspace{15pt}有一个初始为空的序列 aa。现在有 qq 个操作,请按照给出的顺序依次处理。每个操作是以下三种之一:

∙ \hspace{23pt}\bullet\,操作 11:给定一个整数 xx,将 xx 添加到序列 aa 的末尾;

∙ \hspace{23pt}\bullet\,操作 22:输出序列 aa 的第一个元素,然后将它从 aa 中删除。保证执行该操作时 aa 不为空;

∙ \hspace{23pt}\bullet\,操作 33:将序列 aa 按升序排序。

\hspace{15pt}全部 qq 个操作都要按照给出的顺序执行,每个操作恰好执行一次。

输入格式

\hspace{15pt}第一行输入一个整数 q(1≦q≦2×105)q \left(1 \leqq q \leqq 2 \times 10^5\right) 代表操作次数。

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

∙ \hspace{23pt}\bullet\,若 ci=1c_i=1,紧接着在同一行输入一个整数 xi(0≦xi≦109)x_i \left(0 \leqq x_i \leqq 10^9\right) 代表要添加到序列末尾的数;

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

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

\hspace{15pt}保证当 ci=2c_i=2 时序列 aa 不为空。

输出格式

\hspace{15pt}设操作 22 总共出现了 q′q' 次。输出 q′q' 行,第 jj 行输出第 jj 次操作 22 所输出的元素。

测试样例

8
1 4
1 3
1 2
1 1
3
2
1 0
2
1
2

样例 1 解释

\hspace{15pt}依次处理 88 个操作,每个操作完成后序列 aa 的内容如下:

∙ \hspace{23pt}\bullet\,操作 11(x1=4x_1=4):{4}\{4\};

∙ \hspace{23pt}\bullet\,操作 11(x2=3x_2=3):{4,3}\{4,3\};

∙ \hspace{23pt}\bullet\,操作 11(x3=2x_3=2):{4,3,2}\{4,3,2\};

∙ \hspace{23pt}\bullet\,操作 11(x4=1x_4=1):{4,3,2,1}\{4,3,2,1\};

∙ \hspace{23pt}\bullet\,操作 33:升序排序后为 {1,2,3,4}\{1,2,3,4\};

∙ \hspace{23pt}\bullet\,操作 22:输出第一个元素 11,序列变为 {2,3,4}\{2,3,4\};

∙ \hspace{23pt}\bullet\,操作 11(x7=0x_7=0):{2,3,4,0}\{2,3,4,0\};

∙ \hspace{23pt}\bullet\,操作 22:输出第一个元素 22,序列变为 {3,4,0}\{3,4,0\}。

\hspace{15pt}两次操作 22 依次输出 11 和 22,因此答案为 1,21,2。

9
1 5
1 5
1 3
2
3
2
1 6
3
2
5
3
5

样例 2 解释

\hspace{15pt}依次处理 99 个操作,每个操作完成后序列 aa 的内容如下:

∙ \hspace{23pt}\bullet\,操作 11(x1=5x_1=5):{5}\{5\};

∙ \hspace{23pt}\bullet\,操作 11(x2=5x_2=5):{5,5}\{5,5\};

∙ \hspace{23pt}\bullet\,操作 11(x3=3x_3=3):{5,5,3}\{5,5,3\};

∙ \hspace{23pt}\bullet\,操作 22:输出第一个元素 55,序列变为 {5,3}\{5,3\};

∙ \hspace{23pt}\bullet\,操作 33:升序排序后为 {3,5}\{3,5\};

∙ \hspace{23pt}\bullet\,操作 22:输出第一个元素 33,序列变为 {5}\{5\};

∙ \hspace{23pt}\bullet\,操作 11(x7=6x_7=6):{5,6}\{5,6\};

∙ \hspace{23pt}\bullet\,操作 33:升序排序后仍为 {5,6}\{5,6\};

∙ \hspace{23pt}\bullet\,操作 22:输出第一个元素 55,序列变为 {6}\{6\}。

\hspace{15pt}三次操作 22 依次输出 5,3,55,3,5。