2702 高级打字机

因为Undo操作只能撤销Type操作，所以Undo x 实际上就是删除文章末尾x个字母。用一个栈即可解决（每个字母最多进出一次）。

这种情况下只需要设计一个合理的数据结构依次执行操作即可。

版本树：Undo x撤销最近的x次修改操作，实际上就是当前版本还原为x次操作前的版本，换句话说，版本i = 版本i-x-1。

如图所示，所有版本呈树状排列，版本0为根。
读入所有操作并建树，对这颗版本树按欧拉序求出所有版本。上图中就是按0->1->4…4->1->0->2->3->2->0的顺序遍历，同样使用栈就能计算出所有的版本，然后在对应的版本上解决询问即可。
到此，就得到了时空复杂度均为O(n)的离线算法。
能解决这类题目的条件是：

1.允许使用离线算法，进而求出版本树，并允许把询问挂到树的节点上。
2.所有操作都是可逆的。只有所有操作都是可逆的，才能按欧拉序依次求出各版本。如本题的Type操作的逆操作就是弹出栈顶，Undo操作则根本不需要修改（Undo前后2个版本相同）。

#include<cstdio>
using namespace std;
const int R=1e5,N=(R+1)*20;
int n,m,now,sz,root[R+1],ls[N],rs[N],len[N];
char s[N];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void insert(int &k,int last,int l,int r,int pos,int c){
    k=++sz;
    if(l==r){s[k]=c;return ;}
    ls[k]=ls[last];
    rs[k]=rs[last];
    int mid=l+r>>1;
    if(pos<=mid) insert(ls[k],ls[last],l,mid,pos,c);
    else insert(rs[k],rs[last],mid+1,r,pos,c);
}
void query(int &k,int last,int l,int r,int pos){
    if(l==r){putchar(s[k]);putchar('\n');return ;}
    int mid=l+r>>1;
    if(pos<=mid) query(ls[k],ls[last],l,mid,pos);
    else query(rs[k],rs[last],mid+1,r,pos);
}
int main(){
    n=read();
    for(int i=1,x;i<=n;i++){
        char op=0,ch=0;
        for(;op<'A'||op>'Z';op=getchar());
        if(op=='T'){
            for(;ch<'a'||ch>'z';ch=getchar());
            now++;
            len[now]=len[now-1]+1;
            insert(root[now],root[now-1],1,R,len[now],ch);
        }
        else if(op=='U'){
            x=read();
            now++;
            root[now]=root[now-x-1];
            len[now]=len[now-x-1];
        }
        else x=read(),query(root[now],root[now-1],1,R,x);
    }
    return 0;
}