#P1383. 高级打字机

    ID: 427 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>倍增福建省历届夏令营主席树可持久化

高级打字机

题目描述

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

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

  1. T x:Type 操作,表示在文章末尾打下一个小写字母 xx
  2. U x:Undo 操作,表示撤销最后的 xx 次修改操作。
  3. Q x:Query 操作,表示询问当前文章中第 xx 个字母并输出。请注意 Query 操作并不算修改操作。

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

输入格式

11 行:一个整数 nn,表示操作数量。

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

输出格式

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

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

b
c

提示

数据范围及约定

  • 对于 40%40\% 的数据 n200n \le 200
  • 对于 100%100\% 的数据 n100000n \le 100000,同时保证 Undo 操作不会撤销 Undo 操作。

高级挑战

对于 200%200\% 的数据 n100000n \le 100000,Undo 操作可以撤销 Undo 操作。

IOI 挑战

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