P1383 高级打字机

    • 194通过
    • 871提交
  • 题目提供者 yeszy 管理员
  • 评测方式 云端评测
  • 标签 倍增 图论 福建省历届夏令营
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    请为这种高级打字机设计一个程序,支持如下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挑战>

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。