记录编号	583184	评测结果	AAAAAAAAAA
题目名称	高级打字机	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	0.669 s
提交时间	2023-10-05 17:48:19	内存使用	193.80 MiB

#include <bits/stdc++.h>
    using namespace std;
    const int N=1e6+10;
    struct node{
        int l,r;
        char c;
    }t[N*20];
    int n,tot,root[N],cnt,len[N];
    int build(int l,int r){
        int p=++tot;
        if(l==r)return p;
        int mid=(l+r)>>1;
        t[p].l=build(l,mid);
        t[p].r=build(mid+1,r);
        return p;
    }
    int increase(int p,int l,int r,int x,char ch){
        int q=++tot;
        t[q]=t[p];
        if(l==r){
            t[q].c=ch;
        }else{
            int mid=(l+r)>>1;
            if(x<=mid){
                t[q].l=increase(t[q].l,l,mid,x,ch);
            }else{
                t[q].r=increase(t[q].r,mid+1,r,x,ch);
            }
        }
        return q;
    }
    char ask(int p,int l,int r,int x){
        if(l==r)return t[p].c;
        int mid=(l+r)>>1;
        if(x<=mid)return ask(t[p].l,l,mid,x);
        else return ask(t[p].r,mid+1,r,x);
    }
    int main(){
    freopen("type.in","r",stdin); 
    freopen("type.out","w",stdout); 
      cin>>n;
      build(1,n);
      for(int i=1;i<=n;i++){
          char x;
          cin>>x;
          if(x=='T'){
              char y;
              cin>>y;
              cnt++;
              len[cnt]=len[cnt-1]+1;
              root[cnt]=increase(root[cnt-1],1,n,len[cnt],y);
          }else if(x=='U'){
              int o;
              cin>>o;
              cnt++;
              root[cnt]=root[cnt-o-1];
              len[cnt]=len[cnt-o-1];  
              
          }else{
              int op;
              cin>>op;
              cout<<ask(root[cnt],1,n,op)<<endl;
          }
      }
       return 0;      
    }