感激不尽

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ls tr[now].lso
#define rs tr[now].rso
struct nood{
	ll z,lso,rso,siz;
}tr[80000000];
ll n,m,cnt,L,R,K,a[20000000],rt[20000000],sum[20000000],tot;
ll b[20000000],q;
ll bui(ll l,ll r,ll &now){
	now=++cnt;
	if(l==r){
		return now;
	}
	ll mid=(l+r)>>1;
	tr[now].lso=bui(l,mid,ls);
	tr[now].rso=bui(mid+1,r,rs);
	return now;
}
ll update(ll &now,ll lst,ll l,ll r,ll val){
	//当前节点 now，上一个版本对应节点 lst，左端点 l，右端点 r，修改的位置 pos 和修改的值 val
	now=++cnt;
	tr[now]=tr[lst];
	if(l==r){
		tr[now].siz=1;
		tr[now].z=val;
		return now;
	}
	ll mid=(l+r)>>1;
	if(tr[ls].siz<mid-ls+1){
		tr[now].lso=update(ls,tr[lst].lso,l,mid,val);
	}
	else{
		tr[now].rso=update(rs,tr[lst].rso,mid+1,r,val);
	}
	return now;
}
ll que(ll now,ll l,ll r,ll pos){
	ll mid=(l+r)>>1;
	if(l==r){
		return tr[now].z;
	}
	if(pos<=tr[ls].siz){
		return que(tr[now].lso,l,mid,pos);
	}
	else{
		return que(tr[now].rso,mid+1,r,pos);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
//	bui(1,n,rt[0]);
	char op,s;ll xx; 
	for(int i=1;i<=n;i++){
		cin>>op;
		if(op=='T'){
			cin>>s;
			tot++;
			update(rt[tot],rt[tot-1],1,n,s-'a');
		}
		if(op=='U'){
			cin>>xx;
			tot++;
			rt[tot]=rt[tot-xx-1];
		}
		if(op=='Q'){
			cin>>xx;
			cout<<char(que(rt[tot],1,n,xx)+'a')<<"*\n";
		}
	}
}