CF2011I Stack and Queue
题目描述
两名医生的门口排着两队病人。第一位医生按照通常的排队顺序看病人——谁先到，谁就先看。第二位医生做了相反的事情——他先给最后到达的人看病。因此，有第一位医生的队列和第二位医生的堆栈。患者既可以在队列中，也可以在堆栈中。每位患者的特征是他们去看医生的时间（两位医生的时间相同）。
预约开始时，医生将分别按照排队和堆叠的顺序看病人。医生一做完一个病人，就会给下一个病人打电话。
但有一个问题：如果一个病人同时在队列和堆栈中，他先被叫到一个医生那里，然后被叫到另一个医生那儿，而他还没有完成第一个医生的工作，就会出现混乱。允许患者在与第一位医生交谈结束的那一刻去看第二位医生。
如果医生能够看到所有患者而不会产生任何混淆，那么队列和堆栈的当前配置就被称为良好。
最初，队列和堆栈都是空的。有三种类型的查询：
1. 将患者x添加到队列中；
2.将患者x添加到堆栈中；
3.排队的病人x意识到自己走错了地方，于是移到了队列中；
然而，他移动到堆栈中的位置，就像他在进入队列时进入堆栈一样。
保证每次查询后，每个患者在队列中不超过一次，在堆栈中不超过1次。
每次查询后，您都需要确定当前配置是否良好。
输入格式
第一行包含一个整数$n$($1 \le n \le 10^5$)--请求的数量。
第二行包含$n$个整数 $a_1,a_2,...a_n(1 \leq a_i \leq 10^9)$--对于每位患者，他们去看医生的时间。
以下$n$行中的每一行都包含两个整数$t$和$x(1 \leq t \leq3；1\leq x \leq n)$——查询类型和患者索引。
如果查询类型为1，则患者x尚未在队列中；
如果查询类型为2，则患者x还不在堆栈中；
如果查询类型为3，则患者x已经在队列中，还没有在堆栈中。
输出格式
每次查询后，如果当前配置良好，则打印“YES”，否则打印“NO”。
说明/提示
In the first test, there are the following configurations:
1. queue: $ [1] $ ; stack: $ [] $ ; patient $ 1 $ is seen by the first doctor for $ 10 $ minutes, starting at minute $ 0 $ .
2. queue: $ [1] $ ; stack: $ [1] $ ; patient $ 1 $ is seen by the first doctor during $ [0; 10) $ and by the second during $ [0; 10) $ . Since patient $ 1 $ must be at both doctors at the same time, the answer is "NO".
3. queue: $ [1] $ ; stack: $ [1, 2] $ ; patient $ 1 $ is seen by the first doctor during $ [0; 10) $ , and by the second during $ [15; 25) $ ; patient $ 2 $ is seen by the second doctor during $ [0, 15) $ . Now patient $ 1 $ can make it to the second doctor after seeing the first.
In the second test, the configuration after query $ 4 $ is as follows:
- queue: $ [1, 2] $ ;
- stack: $ [5, 3] $ ;
- patient $ 1 $ : first doctor $ [0, 2) $ , second doctor is not seeing him;
- patient $ 2 $ : first doctor $ [2, 7) $ , second doctor is not seeing him;
- patient $ 3 $ : first doctor is not seeing him, second doctor $ [0, 1) $ ;
- patient $ 5 $ : first doctor is not seeing him, second doctor $ [1, 6) $ .
After request $ 5 $ , the next configuration is:
- queue: $ [1] $ ;
- stack: $ [5, 2, 3] $ ;
- patient $ 1 $ : first doctor $ [0, 2) $ , second doctor is not seeing him;
- patient $ 2 $ : first doctor is not seeing him, second doctor $ [1, 6) $ ;
- patient $ 3 $ : first doctor is not seeing him, second doctor $ [0, 1) $ ;
- patient $ 5 $ : first doctor is not seeing him, second doctor $ [6, 11) $ .
After request $ 6 $ , the next configuration is:
- queue: $ [1, 2] $ ;
- stack: $ [5, 2, 3] $ ;
- patient $ 1 $ : first doctor $ [0, 2) $ , second doctor is not seeing him;
- patient $ 2 $ : first doctor $ [2, 7) $ , second doctor $ [1, 6) $ ;
- patient $ 3 $ : first doctor is not seeing him, second doctor $ [0, 1) $ ;
- patient $ 5 $ : first doctor is not seeing him, second doctor $ [6, 11) $ .
Patient $ 2 $ must be at both doctors at the same time.
After request $ 7 $ , the next configuration is:
- queue: $ [2] $ ;
- stack: $ [1, 5, 2, 3] $ ;
- patient $ 1 $ : first doctor is not seeing him, second doctor $ [11, 13) $ ;
- patient $ 2 $ : first doctor $ [0, 5) $ , second doctor $ [1, 6) $ ;
- patient $ 3 $ : first doctor is not seeing him, second doctor $ [0, 1) $ ;
- patient $ 5 $ : first doctor is not seeing him, second doctor $ [6, 11) $ .
Patient $ 2 $ must be at both doctors at the same time.