by luogu
可持久练习题
3个操作
1.T x：在文章末尾打下一个小写字母 xx。（type 操作 )
2.U x：撤销最后的 xx 次修改操作。（Undo 操作）
（注意 Query 操作并不算修改操作）
-
Q x：询问当前文章中第 xx 个字母并输出。（Query 操作）
文章一开始可以视为空串。
#include<bits/stdc++.h> #define mid ((l+r)>>1) using namespace std; const int N=100020; int root[N<<5],len[N]; int n,m; struct node { int ls,rs;//-> 左右儿子 int num;//本身的值 }a[N<<5]; int _=1; void add(int &now,int x,int l,int r,int k) { a[_++]=a[now]; //复制 //标 号 + + now=_-1;//一个新点 if(l==r) {//传值 a[now].num=k; return ; } //正常的线段树流程 if(x<=mid) add(a[now].ls,x,l,mid,k); else add(a[now].rs,x,mid+1,r,k); return ; } int query(int x,int p,int l,int r) {//注意p if(l==r)//返回 return a[x].num; //正常的query if(p<=mid) return query(a[x].ls,p,l,mid); else return query(a[x].rs,p,mid+1,r); } int cnt; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) { char flag; cin>>flag; if(flag==‘T‘) { char x; cin>>x; cnt++; //开点 root[cnt]=root[cnt-1]; len[cnt]=len[cnt-1]+1; add(root[cnt],len[cnt],1,n,x-‘a‘); //字符转数字 } else { int x;cin>>x; if(flag==‘U‘) { cnt++; //继承历史版本 root[cnt]=root[cnt-x-1]; len[cnt]=len[cnt-x-1]; } else { cout<<(char)(query(root[cnt],x,1,n)+‘a‘)<<endl;; } } } return 0; }