#include <bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int n,m,a[N],root[N],cnt,len[N];
struct node{int L,R,sum;}tree[N];
void update(int &p,int pre,int pl,int pr,int L,int x){
	p=++cnt;
	tree[p].L=tree[pre].L,tree[p].R=tree[pre].R;
	tree[p].sum=tree[pre].sum;
	if(pl==pr){
		tree[p].sum=x;
		return;
	}
	int mid=(pl+pr)>>1;
	if(L<=mid)update(tree[p].L,tree[pre].L,pl,mid,L,x);
	else update(tree[p].R,tree[pre].R,mid+1,pr,L,x);
}
int query(int p,int pl,int pr,int L){ 
	if (!p) return 0;
	if(pl==pr)return tree[p].sum;
	int mid=(pl+pr)>>1;
	if(L<=mid)return query(tree[p].L,pl,mid,L);
	else return query(tree[p].R,mid+1,pr,L);
}
int main(){
	cin>>n;
	while(n--){
		char c,x;
		int xx;
		cin>>c;
		if(c=='T'){
			cin>>x;
			m++;
			len[m]=len[m-1]+1;
			update(root[m],root[m-1],1,N-1,len[m],x);
		}else if(c=='U'){
			cin>>xx;
			m++;
			root[m]=root[m-xx-1];
			len[m]=len[m-xx-1];
		}else{
			cin>>xx;
			cout<<char(query(root[m],1,N-1,xx))<<endl;
		}
	}
	return 0;
}

原来我的 query 和 update 的右端点是 n

也就是

query(root[m],1,n,xx)

为什么 n 不对