记录编号	583182	评测结果	AAAAAAAAAA
题目名称	高级打字机	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.621 s
提交时间	2023-10-05 17:40:15	内存使用	145.73 MiB

#include<iostream>
#include<cstdio>
using namespace std;
long long fa=0,f[1000010][21],tot=0,l[1000010],n,yx=0,d[1000010]={},c2[25];
char t[1000010];
int main()
{
    freopen("type.in","r",stdin);
    freopen("type.out","w",stdout);
    c2[0]=1;
    for(int i=1;i<=20;i++)
    {
        c2[i]=c2[i-1]*2;
    }
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        char a;
        cin>>a;
        if(a=='T'){
            yx++;
            tot++;
            cin>>t[tot];
            l[yx]=tot;
            d[tot]=d[fa]+1;
            f[tot][0]=fa;
            for(int j=1;j<=20;j++)
            {
                f[tot][j]=f[f[tot][j-1]][j-1];
            }
            fa=tot;
        }else if(a=='Q'){
            int x;
            cin>>x;
            long long fa2=fa;
            for(int j=20;j>=0;j--)
            {
                if(d[fa2]-c2[j]>=x)
                {
                    fa2=f[fa2][j];
                }
                if(d[fa2]==x)
                {
                    cout<<t[fa2]<<endl;
                    break;
                }
            }
        }else{
            int x;
            cin>>x;
            yx++;
            l[yx]=l[yx-x-1];
            fa=l[yx];
        }
    }
    return 0;
}