记录编号	583178	评测结果	AAAAAAAAAA
题目名称	高级打字机	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.161 s
提交时间	2023-10-05 17:26:42	内存使用	15.27 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int n;
struct made{
    int ls,rs,size;
    char ch;
}t[N<<4];
int root[N],cnt,tot;
void build(int &x,int l,int r){
    x = ++tot;
    t[x].size = 0;
    if(l == r)return;
    int mid = l + r >> 1;
    build(t[x].ls,l,mid);
    build(t[x].rs,mid+1,r);
}
void add(int la,int &now,int l,int r,char ch){
    now = ++tot;
    t[now] = t[la];
    if(l == r){
        t[now].size = 1;
        t[now].ch = ch;
        return;
    }
    int mid = l + r >> 1;
    if(t[t[la].ls].size < mid-l+1)add(t[la].ls,t[now].ls,l,mid,ch);
    else add(t[la].rs,t[now].rs,mid+1,r,ch);
    t[now].size = t[t[now].ls].size + t[t[now].rs].size;
}
char ask(int now,int l,int r,int x){
    if(l == r)return t[now].ch;
    int mid = l + r >> 1;
    if(x <= t[t[now].ls].size)return ask(t[now].ls,l,mid,x);
    else return ask(t[now].rs,mid+1,r,x-t[t[now].ls].size);
}
int main(){
    freopen("type.in","r",stdin);
    freopen("type.out","w",stdout);
    scanf("%d",&n);
    build(root[0],1,n);
    for(int i = 1;i <= n;i++){
        char c[3],cc[3];scanf("%s",c);
        int x;
        if(c[0] == 'T'){
            scanf("%s",cc);
            ++cnt;
            add(root[cnt-1],root[cnt],1,n,cc[0]);
        }
        else if(c[0] == 'Q'){
            scanf("%d",&x);
            printf("%c\n",ask(root[cnt],1,n,x));
        }
        else{
            scanf("%d",&x);
            cnt++;
            root[cnt] = root[cnt-x-1];
        }
    }
    
    return 0;
    
}