Rt

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define re register int
#define il inline
#define mid ((l+r)>>1)
using namespace std;
il int read()
{
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
  return x*f;
}
const int N=1e6+5;
int n,root[N],cnt,num;
struct node{
	int l,r,sum;char c;
}t[N<<5];
il int new_node(int x){++cnt;t[cnt]=t[x];return cnt;}
il int build(int l,int r)
{
	++cnt;
	if(l<r)t[cnt].l=build(l,mid),t[cnt].r=build(mid+1,r);
	return cnt;
}
il int change(int k,int l,int r,int x,char c)
{
	int y=new_node(k);t[y].sum++;
	if(l==r){t[y].c=c;t[y].sum=1;return y;}
	if(x<=mid)t[y].l=change(t[y].l,l,mid,x,c);
	else t[y].r=change(t[y].r,mid+1,r,x,c);
	return y;
}
il void query(int k,int l,int r,int x)
{
	if(l==r){printf("%c\n",t[k].c);return;}
	if(x<=mid)return query(t[k].l,l,mid,x);
	return query(t[k].r,mid+1,r,x);
}
char c,d;
signed main()
{
	n=read();
	root[0]=build(1,n);
	for(re i=1,x;i<=n;i++)
	{
		cin>>c;
		if(c=='T')cin>>d,num++,root[num]=change(root[num-1],1,n,t[root[num-1]].sum+1,d);
		else if(c=='U')x=read(),num++,root[num]=new_node(root[num-x-1]);
		else x=read()+1,query(root[num],1,n,x);
	}
	return 0;
}

dalao帮帮忙，会爆空间