只有10分/kk

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5;
struct tree{
	int l,r;
	char val;
}t[N*50];
int siz[N];
int cnt;
inline int clone(int p){
	cnt++;
	t[cnt]=t[p];
	siz[cnt]=siz[p];
	return cnt;
}
int add(int p,int l,int r,char ch){
	p=clone(p);
	if(l==r){
		siz[p]=1;
		t[p].val=ch;
		return p;
	}
	int mid=(l+r)>>1;
	if(siz[t[p].l]==mid-l+1) t[p].r=add(t[p].r,mid+1,r,ch);
	else t[p].l=add(t[p].l,l,mid,ch);
	siz[p]=siz[t[p].l]+siz[t[p].r];
	return p;
}
char query(int p,int l,int r,int k){
	if(l==r) return t[p].val;
	int mid=(l+r)>>1;
	if(siz[t[p].l]>=k) return query(t[p].l,l,mid,k);
	else return query(t[p].r,mid+1,r,k-siz[t[p].l]);
}
int root[N],node;
int n;
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		string opt;
		cin>>opt;
		if(opt=="T"){
			char ch;
			cin>>ch;
			node++;
			root[node]=add(root[node-1],1,n,ch);
		}
		if(opt=="U"){
			int x;
			cin>>x;
			node++;
			root[node]=root[node-x-1];
			siz[node]=siz[node-x-1];
		}
		if(opt=="Q"){
			int x;
			cin>>x;
			cout<<query(root[node],1,n,x)<<endl;
		}
	}
}