← 返回题目列表

Codeforces · 2011/I

I. 堆栈和队列

中文机器翻译题面 查看原题

两个医生门口有$$$2$$$的病人排队。第一个医生按照通常的队列顺序为病人看病——先到的人会先被看诊。第二位医生则相反——他先看最后到的人。因此,第一个医生有一个队列,第二个医生有一个堆栈。患者既可以在队列中,也可以在堆栈中。每个患者的特征都是看医生所需的时间(两位医生的时间相同)。

预约开始时,医生将分别按照排队和堆叠的顺序看诊患者。医生一处理完一个病人,就会给下一个病人打电话。

但是有一个问题:如果一个病人同时在队列和堆栈中,他先被叫到一位医生,然后又叫到另一位医生,而他还没有完成第一个医生的工作,就会出现混乱。允许患者在与第一位医生结束后立即去看第二位医生。

如果医生可以看到所有患者而不会产生任何混乱,则队列和堆栈的当前配置称为良好。

最初,队列和堆栈都是空的。查询分为三种类型:

1. 将患者 $$$x$$$ 添加到队列中;
2. 将患者 $$$x$$$ 添加到堆栈中;
3. 队列中的患者 $$$x$$$ 意识到自己放错了位置,并移至堆栈;然而,他移动到堆栈中的位置,就好像他在进入队列时在查询时进入堆栈一样。

保证每次查询后,每个患者在队列中不超过一次,在堆栈中不超过一次。

每次查询后,需要判断当前配置是否良好。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 请求数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 对于每个患者,他们去看医生所需的时间。

以下 $$$n$$$ 行中的每一行都包含两个整数 $$$t$$$ 和 $$$x$$$ ($$$1 \le t \le 3$$$; $$$1 \le x \le n$$$) — 查询类型和患者索引。保证:

- 如果查询的类型为 $$$1$$$,则患者 $$$x$$$ 尚未在队列中;
- 如果查询的类型为 $$$2$$$,则患者 $$$x$$$ 尚未在堆栈中;
- 如果查询的类型为 $$$3$$$,则患者 $$$x$$$ 已在队列中,但尚未在堆栈中。

输出

每次查询后,如果当前配置良好,则打印“YES”,否则打印“NO”。

示例

输入 #1

3
10 15 4
1 1
2 1
2 2

输出 #1

YES
NO
YES

输入 #2

7
2 5 1 5 5 4 8
1 1
2 5
1 2
2 3
3 2
1 2
3 1

输出 #2

YES
YES
YES
YES
YES
NO
NO

注意

第一次测试时,有以下配置:

1.队列:$$$[1]$$$;堆栈:$$$[]$$$;患者 $$$1$$$ 由第一位医生看诊 $$$10$$$ 分钟,从 $$$0$$$ 分钟开始。
2.队列:$$$[1]$$$;堆栈:$$$[1]$$$;病人$$$1$$$在$$$[0期间由第一位医生看诊; 10)$$$ 以及 $$$[0 期间的第二个; 10)$$$。由于患者 $$$1$$$ 必须同时去看两位医生,所以答案是“否”。
3.队列:$$$[1]$$$;堆栈: $$$[1, 2]$$$;病人$$$1$$$在$$$[0期间由第一位医生看诊; 10)$$$,以及$$$[15期间的第二个; 25)$$$;患者 $$$2$$$ 在 $$$[0, 15)$$$ 期间由第二位医生看诊。现在,患者 $$$1$$$ 可以在看过第一位医生后去找第二位医生。

第二次测试中,查询$$$4$$$后的配置如下:

- 队列: $$$[1, 2]$$$;
- 堆栈: $$$[5, 3]$$$;
- 病人 $$$1$$$: 第一个医生 $$$[0, 2)$$$,第二个医生没有给他看病;
- 病人 $$$2$$$: 第一个医生 $$$[2, 7)$$$,第二个医生没有给他看病;
- 病人 $$$3$$$: 第一个医生没有给他看病,第二个医生 $$$[0, 1)$$$;
- 病人$$$5$$$:第一个医生没有给他看病,第二个医生$$$[1, 6)$$$。

请求$$$5$$$后,下一个配置是:

- 队列:$$$[1]$$$;
- 堆栈: $$$[5, 2, 3]$$$;
- 病人 $$$1$$$: 第一个医生 $$$[0, 2)$$$,第二个医生没有给他看病;
- 病人 $$$2$$$: 第一个医生没有给他看病,第二个医生 $$$[1, 6)$$$;
- 病人 $$$3$$$: 第一个医生没有给他看病,第二个医生 $$$[0, 1)$$$;
- 病人 $$$5$$$:第一个医生没有给他看病,第二个医生 $$$[6, 11)$$$。

请求$$$6$$$后,下一个配置是:

- 队列: $$$[1, 2]$$$;
- 堆栈: $$$[5, 2, 3]$$$;
- 病人 $$$1$$$: 第一个医生 $$$[0, 2)$$$,第二个医生没有给他看病;
- 病人 $$$2$$$: 第一个医生 $$$[2, 7)$$$, 第二个医生 $$$[1, 6)$$$;
- 病人 $$$3$$$: 第一个医生没有给他看病,第二个医生 $$$[0, 1)$$$;
- 病人 $$$5$$$:第一个医生没有给他看病,第二个医生 $$$[6, 11)$$$。

患者 $$$2$$$ 必须同时到两位医生处。

请求$$$7$$$后,下一个配置是:

- 队列:$$$[2]$$$;
- 堆栈: $$$[1, 5, 2, 3]$$$;
- 病人 $$$1$$$: 第一个医生没有给他看病,第二个医生 $$$[11, 13)$$$;
- 病人 $$$2$$$: 第一个医生 $$$[0, 5)$$$, 第二个医生 $$$[1, 6)$$$;
- 病人 $$$3$$$: 第一个医生没有给他看病,第二个医生 $$$[0, 1)$$$;
- 病人 $$$5$$$:第一个医生没有给他看病,第二个医生 $$$[6, 11)$$$。

患者 $$$2$$$ 必须同时到两位医生处。