[THUPC2019] 组合数据结构问题

题目描述

> 众所周知,小葱同学擅长计算,尤其擅长计算组合数,但这个题和组合数没什么关系。 小葱同学在学习了组合数的计算之后,开始了研究数据结构的道路。通过十五分钟的刻苦学习,小葱同学初步掌握了队列、栈和堆这三种数据结构。小葱同学发现这三种数据结构都支持两种操作: 1. 将某个数插入该数据结构。 2. 从该数据结构中按照数据结构的原理取出一个数。 小葱同学为了检验自己对这三种数据结构的理解,设计了一个类似的黑箱模型。该模型也支持两种操作,向黑箱中输入一个数或者从黑箱中输出一个数。现在小葱对该黑箱做了若干次操作,并给出每次输入和输出的数,问这个黑箱实现的是否可能是队列、栈、大根堆或者小根堆。 虽然小葱同学对这四种数据结构了如指掌,但他还是决定告诉你它们的分别是什么: - 如果黑箱是**队列**:黑箱初始为空,输入时数将被放入黑箱,输出时当前黑箱内**最早被放入的**数将被输出并移出黑箱。 - 如果黑箱是**栈**:黑箱初始为空,输入时数将被放入黑箱,输出时当前黑箱内**最晚被放入的**数将被输出并移出黑箱。 - 如果黑箱是**大根堆**:黑箱初始为空,输入时数将被放入黑箱,输出时当前黑箱内**值最大的**数将被输出并移出黑箱。特别地,如值最大的数有多个,则仅将其中一个移出黑箱。 - 如果黑箱是**小根堆**:黑箱初始为空,输入时数将被放入黑箱,输出时当前黑箱内**值最小的**数将被输出并移出黑箱。特别地,如值最小的数有多个,则仅将其中一个移出黑箱。

输入输出格式

输入格式


第一行一个整数 $N$ 代表操作的个数。 接下来 $N$ 行每行两个整数 $\mathrm{opt},v$ 。如果 $\mathrm{opt}=1$ ,代表这次操作小葱同学向黑箱中插入 $v$ 了这个数;如果 $\mathrm{opt=2}$ ,代表小葱这次操作从黑箱中取出了 $v$ 这个数。 保证 $0\leq N\leq 10^5$ ,$-2^{31}\leq v<2^{31}$ ,$\mathrm{opt}\in\{1,2\}$ 。 注意输入的数据仅保证在格式和范围上完全正确,不保证任何其他条件。

输出格式


共四行,每行可能是 `Yes` 或者 `No`,分别依次代表该黑箱是否可能是队列、栈、大根堆或者小根堆。

输入输出样例

输入样例 #1

6
1 1
1 2
1 3
2 1
2 2
2 3

输出样例 #1

Yes
No
No
Yes

说明

##### 版权信息 来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。 题解等资源可在 <https://github.com/wangyurzee7/THUPC2019> 查看。