时间限制: 1 s
空间限制: 256000 KB
题目等级 : 大师 Master
题目描述 Description
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下3种操作：
1.T x：在文章末尾打下一个小写字母x。(type操作)
2.U x：撤销最后的x次修改操作。（Undo操作）
（注意Query操作并不算修改操作）
3.Q x：询问当前文章中第x个字母并输出。（Query操作）
文章一开始可以视为空串。
输入描述 Input Description
第1行：一个整数n，表示操作数量。
以下n行，每行一个命令。保证输入的命令合法。
输出描述 Output Description
每行输出一个字母，表示Query操作的答案。
样例输入 Sample Input
7
T a
T b
T c
Q 2
U 2
T c
Q 2
样例输出 Sample Output
b
c
数据范围及提示 Data Size & Hint
对于40%的数据 n<=200;
对于50%的数据 n<=100000；保证Undo操作不会撤销Undo操作。
<高级挑战>
对于100%的数据 n<=100000；Undo操作可以撤销Undo操作。
裸主席树
屠龙宝刀点击就送
#include <cstdio> #define N 2005000 char str[N]; int ls[N],rs[N],R=N/20,n,len[N],rt[N],now,tot; void update(int l,int r,int x,int &y,int t,char v) {y=++tot;if(l==r) {str[y]=v;return;}ls[y]=ls[x];rs[y]=rs[x];int mid=(l+r)>>1;if(t<=mid) update(l,mid,ls[x],ls[y],t,v);else update(mid+1,r,rs[x],rs[y],t,v); } void ask(int l,int r,int x,int y,int t) {if(l==r) {printf("%c\n",str[y]);return;}int mid=(l+r)>>1;if(t<=mid) ask(l,mid,ls[x],ls[y],t);else ask(mid+1,r,rs[x],rs[y],t); } int main() {scanf("%d",&n);char opt[5],ch;for(int x;n--;){scanf("%1s",opt);ch=getchar();if(opt[0]=='T'){ch=getchar();len[++now]=len[now-1]+1;update(1,R,rt[now-1],rt[now],len[now],ch);}else if(opt[0]=='U'){scanf("%d",&x);len[++now]=len[now-x-1];rt[now]=rt[now-x-1];}else {scanf("%d",&x);ask(1,R,rt[now-1],rt[now],x);}ch=getchar();}return 0; }