问题 2702 --高级打字机

2702: 高级打字机

题目描述

  早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。
请为这种高级打字机设计一个程序,支持如下3种操作:
1.T x:在文章末尾打下一个小写字母x。(type操作)
2.U x:撤销最后的x次修改操作。(Undo操作)
(注意Query操作并不算修改操作)
3.Q x:询问当前文章中第x个字母并输出。(Query操作)
文章一开始可以视为空串。

输入

第1行:一个整数n,表示操作数量。
以下n行,每行一个命令。保证输入的命令合法。

输出

每行输出一个字母,表示Query操作的答案。

样例输入输出

输入#1 复制
7
T a
T b
T c
Q 2
U 2
T c
Q 2
输出#1 复制
b
c

提示

【数据范围】
对于40%的数据 n<=200;
对于100%的数据 n<=100000;保证Undo操作不会撤销Undo操作。
<高级挑战>
对于200%的数据 n<=100000;Undo操作可以撤销Undo操作。
<IOI挑战>
必须使用在线算法完成该题。

序号 标题 作者 发表时间 费用 订购数 操作