P1383 高级打字机
题目描述
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能。
请为这种高级打字机设计一个程序。文章初始为空,程序需要支持以下 3 种操作:
∙类型为 ‘T’ 的操作:在文章末尾打下一个字符 c;
∙类型为 ‘U’ 的操作:撤销最近 x 次修改操作;
∙类型为 ‘Q’ 的操作:询问当前文章中的第 y 个字符并输出。
其中,‘T’ 操作与 ‘U’ 操作都算作一次修改操作,‘Q’ 操作不算修改操作。‘U’ 操作会撤销最近的 x 次修改操作,也就是把文章恢复到执行这 x 次修改操作之前的状态;被撤销的修改操作本身也可以是 ‘U’ 操作,因此撤销可以叠加。
例如,若先执行 ‘U 2’ 撤销了此前的两次修改,再执行 ‘U 1’,则撤销的是这次 ‘U 2’ 操作,文章会回到执行 ‘U 2’ 之前的状态。
输入格式
第一行输入一个整数 n(1≦n≦105) 代表操作次数。
此后 n 行,每行输入一个操作。每行先输入一个字符 op 代表操作类型,随后在同一行:
∙若 op=‘T’,输入一个小写字母 c,代表在文章末尾打下的字符;
∙若 op=‘U’,输入一个整数 x(1≦x≦cnt),代表撤销的修改次数;
∙若 op=‘Q’,输入一个整数 y(1≦y≦len),代表询问的位置。
其中,cnt 代表该次操作前已经执行过的修改操作次数,len 代表该次操作前文章的长度。保证输入的操作合法。
输出格式
对于每次 ‘Q’ 操作,在一行上输出一个字符,代表当前文章中第 y 个字符。
测试样例
7
T a
T b
T c
Q 2
U 2
T c
Q 2
b
c
样例 1 解释
初始时文章为空,操作过程如下:
∙执行 "T a" 与 "T b" 与 "T c" 后,文章为 "abc";
∙执行 "Q 2":询问第 2 个字符,得到 ‘b’;
∙执行 "U 2":撤销最近 2 次修改操作,即撤销 "T c" 与 "T b",文章变为 "a";
∙执行 "T c":在末尾打下 ‘c’,文章变为 "ac";
∙执行 "Q 2":询问第 2 个字符,得到 ‘c’。
因此依次输出 ‘b’ 与 ‘c’。
8
T a
T b
U 1
T c
U 2
Q 1
T d
Q 2
a
b
样例 2 解释
初始时文章为空,操作过程如下:
∙执行 "T a" 与 "T b" 后,文章为 "ab";
∙执行 "U 1":撤销最近 1 次修改操作,即撤销 "T b",文章变为 "a",这次撤销本身也算一次修改操作;
∙执行 "T c":文章变为 "ac";
∙执行 "U 2":撤销最近 2 次修改操作,即撤销 "T c" 与上一次 "U 1",文章回到执行 "U 1" 之前的状态 "ab";
∙执行 "Q 1":询问第 1 个字符,得到 ‘a’;
∙执行 "T d":文章变为 "abd";
∙执行 "Q 2":询问第 2 个字符,得到 ‘b’。
因此依次输出 ‘a’ 与 ‘b’。
提示
对于前 20% 的数据,1≦n≦200。
对于前 50% 的数据,保证 ‘U’ 操作不会撤销 ‘U’ 操作。
对于 100% 的数据,1≦n≦105。