配点: 1000 点
問題文
您正在管理景点的队列。一开始,没有人排队。从现在开始 Q 查询需要处理。每个查询都是 4 其中一种。
- A 型: 给出了 文字列 X_i ,并且名称被放置在矩阵的末尾。 X_i 一个人进来了。
- B 型: 给出 文字列 X_i 并将名称放置在矩阵的中心。 X_i 一个人进来了。
- C 型: 排在前面的人离开队伍。
- D 型: 回答队列前面的人的姓名。
但是,在 B 类查询中,排队的人数 n 当你是一个人时, 如果n 是奇数,则从头开始 (n+1)/2 在眼睛后面, 如果n 是偶数,则从头开始。 n/2 你应该进入对方的眼睛后面(尤其是 n = 0 表示它将位于矩阵的末尾)。
编写一个程序,按顺序处理所有查询并正确回答给定的 D 类型查询。
注意
本题中,如果满足执行时间限制,则答案正确(AC),但计算量为 让我们用 O(Q) 来解决它。
制約
- 2 \leq Q \leq 300000
- i 当查询类型为A、B时,X_i 由小写字母组成 打印第 10 个字符的字符串
- 当队列中无人时,永远不会执行类型 C 和 D 的查询。
- 类型 D 的查询是 执行次数超过 1 次 指向第
入力
输入是按以下格式从标准输入给出的。
Q Query_1 Query_2 \vdots Query_Q
但是, 运算前设定中包含的Query_i 是 您也可以写 i 个查询的信息。对于每种类型,它以以下格式给出:
当类型 A
A X_i
对于 B 型
B X_i
对于 C 型
C
当类型 D
D
出力
每次 D 类型的查询到来时,队列头部的名字是 1 请逐行输出。
入力例 1
6 A kyopuro A tessoku B book D C D
出力例 1
kyopuro book
每个查询及其结果如下所示:
| 何番目 | 查询 | 説明 | 行列 |
|---|---|---|---|
| 1 | A kyopuro |
位于矩阵末尾 kyopuro 输入 |
[ "kyopuro" ] |
| 2 | A tessoku |
位于矩阵末尾 tessoku 输入 |
[ "kyopuro", "tessoku" ] |
| 3 | B book |
位于矩阵的中心 book 输入 |
[ "kyopuro", "book", "tessoku" ] |
| 4 | D |
回答队列中第一个人的姓名 输出 | (kyopuro ) |
| 5 | C |
排在前面的人离开队伍。 | [ "book", "tessoku" ] |
| 6 | D |
回答队列中第一个人的姓名 输出 | (book ) |
因此,1 线 kyopuro、2 线 book 。
入力例 2
15 B prefixsum B binsearch A dp B math C D C D B heuristics B ds B graph C D C D
出力例 2
binsearch math heuristics graph