#P5375. [THUPC2019] 组合数据结构问题

[THUPC2019] 组合数据结构问题

题目描述

众所周知,小葱同学擅长计算,尤其擅长计算组合数,但这个题和组合数没什么关系。

小葱同学在学习了组合数的计算之后,开始了研究数据结构的道路。通过十五分钟的刻苦学习,小葱同学初步掌握了队列、栈和堆这三种数据结构。小葱同学发现这三种数据结构都支持两种操作:

  1. 将某个数插入该数据结构。
  2. 从该数据结构中按照数据结构的原理取出一个数。

小葱同学为了检验自己对这三种数据结构的理解,设计了一个类似的黑箱模型。该模型也支持两种操作,向黑箱中输入一个数或者从黑箱中输出一个数。现在小葱对该黑箱做了若干次操作,并给出每次输入和输出的数,问这个黑箱实现的是否可能是队列、栈、大根堆或者小根堆。

虽然小葱同学对这四种数据结构了如指掌,但他还是决定告诉你它们的分别是什么:

  • 如果黑箱是队列:黑箱初始为空,输入时数将被放入黑箱,输出时当前黑箱内最早被放入的数将被输出并移出黑箱。
  • 如果黑箱是:黑箱初始为空,输入时数将被放入黑箱,输出时当前黑箱内最晚被放入的数将被输出并移出黑箱。
  • 如果黑箱是大根堆:黑箱初始为空,输入时数将被放入黑箱,输出时当前黑箱内值最大的数将被输出并移出黑箱。特别地,如值最大的数有多个,则仅将其中一个移出黑箱。
  • 如果黑箱是小根堆:黑箱初始为空,输入时数将被放入黑箱,输出时当前黑箱内值最小的数将被输出并移出黑箱。特别地,如值最小的数有多个,则仅将其中一个移出黑箱。

输入格式

第一行一个整数 NN 代表操作的个数。

接下来 NN 行每行两个整数 opt,v\mathrm{opt},v 。如果 opt=1\mathrm{opt}=1 ,代表这次操作小葱同学向黑箱中插入 vv 了这个数;如果 opt=2\mathrm{opt=2} ,代表小葱这次操作从黑箱中取出了 vv 这个数。

保证 0N1050\leq N\leq 10^5231v<231-2^{31}\leq v<2^{31}opt{1,2}\mathrm{opt}\in\{1,2\}

注意输入的数据仅保证在格式和范围上完全正确,不保证任何其他条件。

输出格式

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

6
1 1
1 2
1 3
2 1
2 2
2 3
Yes
No
No
Yes

提示

版权信息

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。