码风淳朴，思路正常，代码抽象

没过样例QAQ

#include<iostream>
#include<cmath>
#include<string>
#include<string.h>
#include<algorithm>

using namespace std;

const int N=1e5+5;

int n;
int rt[N],tot;

struct tree
{
	int l,r,size;
	char c;
}t[N<<5];

int build(int l,int r)
{
	int u=++tot;
	if(l==r)
//	{
//		t[u].size=1;
		return u;
//	}
	int mid=(l+r)/2;
	t[u].l=build(l,mid);
	t[u].r=build(mid+1,r);
//	push_up(u);
	return u;
}

int update(int k,char c,int l,int r,int fa)
{
	int u=++tot;
	t[u].l=t[fa].l,t[u].r=t[fa].r,t[u].c=t[fa].c,t[u].size=t[fa].size;
	if(l==r)
	{
		t[u].c=c;
		//t[u].size=1;
		return u;
	}
	int mid=(l+r)/2;
	if(k<=mid)
		t[u].l=update(k,c,l,mid,t[fa].l);
	else
		t[u].r=update(k,c,mid+1,r,t[fa].r);
	//push_up(u);
	return u;
}

char query(int u,int l,int r,int k)
{
	if(l==r)
		return t[u].c;
	int mid=(l+r)/2;
	if(k<=mid)
		return query(t[u].l,l,mid,k);
	else
		return query(t[u].r,mid+1,r,k);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	rt[0]=build(1,n);
	for(int i=1;i<=n;i++)
	{
		char op,c;
		int x;
		cin>>op;
		if(op=='T')
		{
			cin>>c;
			++tot;
			t[tot].size=t[tot-1].size+1;
			rt[tot]=update(t[tot].size,c,1,n,rt[tot-1]);
		}
		if(op=='U')
		{
			cin>>x;
			++tot;
			rt[tot]=rt[tot-x-1];//撤销操作 
			t[tot].size=t[tot-x-1].size;
		}
		if(op=='Q')
		{
			cin>>x;
			cout<<query(rt[tot],1,n,x)<<endl;
		}
	}
//	for(int i=1;i<=n;i++)
//	{
//		cout<<"t["<<i<<"].l:"<<t[i].l<<" ";
//		cout<<"t["<<i<<"].r:"<<t[i].r<<" ";
//		cout<<"t["<<i<<"].c:"<<t[i].c<<" ";
//		cout<<"t["<<i<<"].size:"<<t[i].size<<endl;
//	}
	return 0;
}