LG#P1383. 高级打字机

高级打字机

P1383 高级打字机

题目描述

\hspace{15pt}早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能。

\hspace{15pt}请为这种高级打字机设计一个程序。文章初始为空,程序需要支持以下 33 种操作:

∙ \hspace{23pt}\bullet\,类型为 ‘T’\texttt{`T'} 的操作:在文章末尾打下一个字符 cc;

∙ \hspace{23pt}\bullet\,类型为 ‘U’\texttt{`U'} 的操作:撤销最近 xx 次修改操作;

∙ \hspace{23pt}\bullet\,类型为 ‘Q’\texttt{`Q'} 的操作:询问当前文章中的第 yy 个字符并输出。

\hspace{15pt}其中,‘T’\texttt{`T'} 操作与 ‘U’\texttt{`U'} 操作都算作一次修改操作,‘Q’\texttt{`Q'} 操作不算修改操作。‘U’\texttt{`U'} 操作会撤销最近的 xx 次修改操作,也就是把文章恢复到执行这 xx 次修改操作之前的状态;被撤销的修改操作本身也可以是 ‘U’\texttt{`U'} 操作,因此撤销可以叠加。

\hspace{15pt}例如,若先执行 ‘U 2’\texttt{`U 2'} 撤销了此前的两次修改,再执行 ‘U 1’\texttt{`U 1'},则撤销的是这次 ‘U 2’\texttt{`U 2'} 操作,文章会回到执行 ‘U 2’\texttt{`U 2'} 之前的状态。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5\right) 代表操作次数。

\hspace{15pt}此后 nn 行,每行输入一个操作。每行先输入一个字符 opop 代表操作类型,随后在同一行:

∙ \hspace{23pt}\bullet\,若 op=‘T’op = \texttt{`T'},输入一个小写字母 cc,代表在文章末尾打下的字符;

∙ \hspace{23pt}\bullet\,若 op=‘U’op = \texttt{`U'},输入一个整数 x(1≦x≦cnt)x \left(1 \leqq x \leqq \mathrm{cnt}\right),代表撤销的修改次数;

∙ \hspace{23pt}\bullet\,若 op=‘Q’op = \texttt{`Q'},输入一个整数 y(1≦y≦len)y \left(1 \leqq y \leqq \mathrm{len}\right),代表询问的位置。

\hspace{15pt}其中,cnt\mathrm{cnt} 代表该次操作前已经执行过的修改操作次数,len\mathrm{len} 代表该次操作前文章的长度。保证输入的操作合法。

输出格式

\hspace{15pt}对于每次 ‘Q’\texttt{`Q'} 操作,在一行上输出一个字符,代表当前文章中第 yy 个字符。

测试样例

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

样例 1 解释

\hspace{15pt}初始时文章为空,操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "T a"\texttt{"T a"} 与 "T b"\texttt{"T b"} 与 "T c"\texttt{"T c"} 后,文章为 "abc"\texttt{"abc"};

∙ \hspace{23pt}\bullet\,执行 "Q 2"\texttt{"Q 2"}:询问第 22 个字符,得到 ‘b’\texttt{`b'};

∙ \hspace{23pt}\bullet\,执行 "U 2"\texttt{"U 2"}:撤销最近 22 次修改操作,即撤销 "T c"\texttt{"T c"} 与 "T b"\texttt{"T b"},文章变为 "a"\texttt{"a"};

∙ \hspace{23pt}\bullet\,执行 "T c"\texttt{"T c"}:在末尾打下 ‘c’\texttt{`c'},文章变为 "ac"\texttt{"ac"};

∙ \hspace{23pt}\bullet\,执行 "Q 2"\texttt{"Q 2"}:询问第 22 个字符,得到 ‘c’\texttt{`c'}。

\hspace{15pt}因此依次输出 ‘b’\texttt{`b'} 与 ‘c’\texttt{`c'}。

8
T a
T b
U 1
T c
U 2
Q 1
T d
Q 2
a
b

样例 2 解释

\hspace{15pt}初始时文章为空,操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "T a"\texttt{"T a"} 与 "T b"\texttt{"T b"} 后,文章为 "ab"\texttt{"ab"};

∙ \hspace{23pt}\bullet\,执行 "U 1"\texttt{"U 1"}:撤销最近 11 次修改操作,即撤销 "T b"\texttt{"T b"},文章变为 "a"\texttt{"a"},这次撤销本身也算一次修改操作;

∙ \hspace{23pt}\bullet\,执行 "T c"\texttt{"T c"}:文章变为 "ac"\texttt{"ac"};

∙ \hspace{23pt}\bullet\,执行 "U 2"\texttt{"U 2"}:撤销最近 22 次修改操作,即撤销 "T c"\texttt{"T c"} 与上一次 "U 1"\texttt{"U 1"},文章回到执行 "U 1"\texttt{"U 1"} 之前的状态 "ab"\texttt{"ab"};

∙ \hspace{23pt}\bullet\,执行 "Q 1"\texttt{"Q 1"}:询问第 11 个字符,得到 ‘a’\texttt{`a'};

∙ \hspace{23pt}\bullet\,执行 "T d"\texttt{"T d"}:文章变为 "abd"\texttt{"abd"};

∙ \hspace{23pt}\bullet\,执行 "Q 2"\texttt{"Q 2"}:询问第 22 个字符,得到 ‘b’\texttt{`b'}。

\hspace{15pt}因此依次输出 ‘a’\texttt{`a'} 与 ‘b’\texttt{`b'}。

提示

\hspace{15pt}对于前 20%20\% 的数据,1≦n≦2001 \leqq n \leqq 200。

\hspace{15pt}对于前 50%50\% 的数据,保证 ‘U’\texttt{`U'} 操作不会撤销 ‘U’\texttt{`U'} 操作。

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1051 \leqq n \leqq 10^5。