TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4267
  • 题目
  • P4267高级打字机
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

    早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。

    请为这种高级打字机设计一个程序,支持如下3种操作:

    1. T x:在文章末尾打下一个小写字母x。(type操作)
    2. U x:撤销最后的x次修改操作。(Undo操作)

    (注意Query操作并不算修改操作)

    1. Q x:询问当前文章中第x个字母并输出。(Query操作)

    文章一开始可以视为空串。

    输入格式

    第1行:一个整数n,表示操作数量。

    以下n行,每行一个命令。保证输入的命令合法。

    输出格式

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

     

    样例输入

    7
    T a
    T b
    T c
    Q 2
    U 2
    T c
    Q 2

    样例输出

    b
    c

    提示

    对于40%的数据 n<=200;

    对于100%的数据 n<=100000;保证Undo操作不会撤销Undo操作。

    <高级挑战>

    对于200%的数据 n<=100000;Undo操作可以撤销Undo操作。

    <IOI挑战>

    必须使用在线算法完成该题。