3333 高级打字机
时间限制: 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操作。
题解：
可持久化线段树维护新加入的字符。遇到撤销操作直接转到root[cnt-x-1]的线段树上。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define maxn 2000000 5 6 using namespace std; 7 8 int root[maxn],ls[maxn],rs[maxn],len[maxn],n,x,cnt,tot; 9 10 char S[maxn<<1],s[10],ch[10]; 11 12 void update(int &y,int x,int l,int r,int pos,char c) 13 { 14 y=++tot; 15 if (l==r) {S[y]=c;return;} 16 ls[y]=ls[x],rs[y]=rs[x]; 17 int mid=(l+r)>>1; 18 if (pos<=mid) update(ls[y],ls[x],l,mid,pos,c); 19 else update(rs[y],rs[x],mid+1,r,pos,c); 20 } 21 22 char query(int rt,int l,int r,int pos) 23 { 24 if (l==r) {return S[rt];} 25 int mid=(l+r)>>1; 26 if (pos<=mid) return query(ls[rt],l,mid,pos); 27 if (pos>mid) return query(rs[rt],mid+1,r,pos); 28 } 29 30 int main() 31 { 32 scanf("%d",&n); 33 for (int i=1;i<=n;i++) 34 { 35 scanf("%s",s); 36 if (s[0]=='T') 37 { 38 cnt++; 39 len[cnt]=len[cnt-1]+1; 40 scanf("%s",ch); 41 update(root[cnt],root[cnt-1],1,100000,len[cnt],ch[0]); 42 } 43 if (s[0]=='U') 44 { 45 scanf("%d",&x); 46 cnt++; 47 root[cnt]=root[cnt-x-1]; 48 len[cnt]=len[cnt-x-1]; 49 } 50 if (s[0]=='Q') 51 { 52 scanf("%d",&x); 53 cout<<query(root[cnt],1,100000,x)<<endl; 54 } 55 } 56 return 0; 57 }