记录编号	583423	评测结果	AAAAAAAAAA
题目名称	高级打字机	最终得分	100
用户昵称	超人	是否通过	通过
代码语言	C++	运行时间	0.725 s
提交时间	2023-10-13 21:53:17	内存使用	167.10 MiB

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+50;
int f[M][25],g[M][25],gjdzj[M],he[M],num[M];
int cnt,n,w;
char s[25],c[25],A[M];
void income()
{
    num[cnt]=num[cnt-1]+1;
    if(A[cnt-1]=='U') gjdzj[cnt]=gjdzj[cnt-1];
    else gjdzj[cnt-1]=cnt-1;
    if(A[cnt-1]=='U') f[cnt][0]=gjdzj[cnt-1];
    else f[cnt][0]=cnt-1;
    he[cnt]= cnt-1;
    for(int i=1;i<=20;i++) f[cnt][i]=f[f[cnt][i-1]][i-1];    
    g[cnt][0]=cnt-1;
    for(int i=1;i<=20;i++) g[cnt][i]=g[g[cnt][i-1]][i-1];
}
void outcome(int x)
{
    x--;
    int now=cnt;
    A[++cnt]='U';
    for(int i=20;i>=0;i--)
    {
        if((1<<i)<=x)
        {
            x-=(1<<i);
            now=g[now][i];
        }
    }
    now--;
    he[cnt]=now;
    num[cnt]=num[now];
    if(A[now]=='U') gjdzj[cnt]=gjdzj[now];
    else gjdzj[cnt]=now;
    if(A[now]=='U') f[cnt][0]=gjdzj[now];
    else f[cnt][0]=now;
    for(int i=1;i<=20;i++) f[cnt][i]=f[f[cnt][i-1]][i-1];
    g[cnt][0]=cnt-1;
    for(int i=1;i<=20;i++) g[cnt][i]=g[g[cnt][i-1]][i-1];
}
int main()
{
    freopen("type.in","r",stdin);
    freopen("type.out","w",stdout);
    cin>>n;
    A[0]='A';
    gjdzj[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        if(s[0]=='T')
        {
            cin>>c;
            A[++cnt]=c[0];
            income();
            continue;
        }
        if(s[0]=='U')
        {
            cin>>w;
            outcome(w);
            continue;
        }
        if(s[0]='Q')
        {
            cin>>w;
            w=num[cnt]-w+1;
            if(w<=0) w=1;
            if(A[cnt]!='U') w--;
            int now=cnt;
            for(int i=20;i>=0;i--)
            if((1<<i)<=w)
            {
                w-=(1<<i);
                now=f[now][i];
            }
            cout<<A[now]<<endl;
        }
    }   
    return 0; 
}