AT_abc217_e [ABC217E] Sorting Queries
题目描述
有一个初始为空的序列 a。现在有 q 个操作,请按照给出的顺序依次处理。每个操作是以下三种之一:
∙操作 1:给定一个整数 x,将 x 添加到序列 a 的末尾;
∙操作 2:输出序列 a 的第一个元素,然后将它从 a 中删除。保证执行该操作时 a 不为空;
∙操作 3:将序列 a 按升序排序。
全部 q 个操作都要按照给出的顺序执行,每个操作恰好执行一次。
输入格式
第一行输入一个整数 q(1≦q≦2×105) 代表操作次数。
此后 q 行,第 i 行输入第 i 个操作,每行先输入一个整数 ci(1≦ci≦3) 代表操作类型,编号同题干:
∙若 ci=1,紧接着在同一行输入一个整数 xi(0≦xi≦109) 代表要添加到序列末尾的数;
∙若 ci=2,该行只有 ci 一个整数;
∙若 ci=3,该行只有 ci 一个整数。
保证当 ci=2 时序列 a 不为空。
输出格式
设操作 2 总共出现了 q′ 次。输出 q′ 行,第 j 行输出第 j 次操作 2 所输出的元素。
测试样例
8
1 4
1 3
1 2
1 1
3
2
1 0
2
1
2
样例 1 解释
依次处理 8 个操作,每个操作完成后序列 a 的内容如下:
∙操作 1(x1=4):{4};
∙操作 1(x2=3):{4,3};
∙操作 1(x3=2):{4,3,2};
∙操作 1(x4=1):{4,3,2,1};
∙操作 3:升序排序后为 {1,2,3,4};
∙操作 2:输出第一个元素 1,序列变为 {2,3,4};
∙操作 1(x7=0):{2,3,4,0};
∙操作 2:输出第一个元素 2,序列变为 {3,4,0}。
两次操作 2 依次输出 1 和 2,因此答案为 1,2。
9
1 5
1 5
1 3
2
3
2
1 6
3
2
5
3
5
样例 2 解释
依次处理 9 个操作,每个操作完成后序列 a 的内容如下:
∙操作 1(x1=5):{5};
∙操作 1(x2=5):{5,5};
∙操作 1(x3=3):{5,5,3};
∙操作 2:输出第一个元素 5,序列变为 {5,3};
∙操作 3:升序排序后为 {3,5};
∙操作 2:输出第一个元素 3,序列变为 {5};
∙操作 1(x7=6):{5,6};
∙操作 3:升序排序后仍为 {5,6};
∙操作 2:输出第一个元素 5,序列变为 {6}。
三次操作 2 依次输出 5,3,5。