题目描述

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

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

1.T x:在文章末尾打下一个小写字母x。(type操作)

2.U x:撤销最后的x次修改操作。(Undo操作)

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

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

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出样例

输入样例#1: 
输出样例#1: 

说明

【数据范围】

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

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

<高级挑战>

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

<IOI挑战>

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

 


emmm水题,IOI挑战比NOIP挑战思维难度简单….

算是练练板子了

注意存一下每个版本的字符串长度

 


说点什么

avatar
  Subscribe  
提醒