P1383

主席树可A，回头试试其他做法

const int N=1e5+86;
int root[N],len[N],tot;
char c[N*30];
struct Node
{
    int l,r;
}tr[N*30];


void build(int &rt,int l,int r){
    rt=++tot;
    if(l==r){
        c[rt]='#';
        return ;
    }
    int mid=(l+r)>>1;
    build(tr[rt].l,l,mid);
    build(tr[rt].r,mid+1,r);
}

void update(int &rt,int last,int l,int r,int pos,char ch){
    rt=++tot;
    if(l==r){
        c[rt]=ch;
        return ;
    }
    tr[rt]=tr[last];
    int mid=(l+r)>>1;
    if(pos<=mid)update(tr[rt].l,tr[last].l,l,mid,pos,ch);
    else update(tr[rt].r,tr[last].r,mid+1,r,pos,ch);
}

char query(int rt,int l,int r,int pos){
    if (l == r)
        return c[rt];
    int mid = (l + r) >> 1;
    if (pos <= mid)
        return query(tr[rt].l, l, mid, pos);
    else
        return query(rt[tr].r, mid + 1, r, pos);
}

LL n,cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    build(root[0],1,n);
    f(i,1,n){
        char a;
        cin>>a;
        if(a=='T'){
            char ch;
            cin>>ch;
            cnt+=1;
            root[cnt]=root[cnt-1];
            len[cnt]=len[cnt-1]+1;
            update(root[cnt],root[cnt-1],1,n,len[cnt],ch);
        }
        else if(a=='U'){
            int d;
            cin>>d;
            cnt+=1;
            root[cnt]=root[cnt-d-1];
            len[cnt]=len[cnt-d-1];
        }
        else if(a=='Q'){
            int d;
            cin>>d;
            cout<<query(root[cnt],1,n,d)<<"\n";
        }
    }
    return 0;
}