P5375 [THUPC 2019] Combined Data Structure Problem

> As everyone knows, student Xiaocong is good at calculations, especially at calculating binomial coefficients, but this problem has little to do with binomial coefficients. After learning how to compute binomial coefficients, Xiaocong started studying data structures. After fifteen minutes of hard study, Xiaocong initially mastered three data structures: queue, stack, and heap. Xiaocong found that these three data structures all support two operations: 1. Insert a number into the data structure. 2. Remove a number from the data structure according to its rules. To test his understanding of these three data structures, Xiaocong designed a similar black-box model. This model also supports two operations: input a number into the black box, or output a number from the black box. Now Xiaocong has performed several operations on this black box and provided the number inserted and the number output each time. You are asked whether this black box could possibly be a queue, a stack, a max-heap, or a min-heap. Although Xiaocong knows these four data structures very well, he still decided to tell you how they differ: - If the black box is a **queue**: the black box is initially empty. On input, the number is placed into the black box. On output, the number that was **inserted earliest** among the current elements in the black box is output and removed. - If the black box is a **stack**: the black box is initially empty. On input, the number is placed into the black box. On output, the number that was **inserted latest** among the current elements in the black box is output and removed. - If the black box is a **max-heap**: the black box is initially empty. On input, the number is placed into the black box. On output, the **largest value** among the current elements in the black box is output and removed. In particular, if there are multiple largest values, only one of them is removed. - If the black box is a **min-heap**: the black box is initially empty. On input, the number is placed into the black box. On output, the **smallest value** among the current elements in the black box is output and removed. In particular, if there are multiple smallest values, only one of them is removed.

The first line contains an integer $N$, which represents the number of operations. The next $N$ lines each contain two integers $\mathrm{opt}, v$. If $\mathrm{opt}=1$, it means that in this operation Xiaocong inserted the number $v$ into the black box. If $\mathrm{opt}=2$, it means that in this operation Xiaocong removed the number $v$ from the black box. It is guaranteed that $0\leq N\leq 10^5$, $-2^{31}\leq v

There are four lines in total. Each line is either `Yes` or `No`, indicating whether the black box could possibly be a queue, a stack, a max-heap, or a min-heap, respectively, in this order.

##### Copyright Information From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019. Solutions and other resources can be found at . Translated by ChatGPT 5