← 返回题目列表

AtCoder · tessoku_book_fo

C17. 奇怪的数据结构?

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

配点: 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