RT

个人感觉写得没有错误

我的siz是记录叶子节点开到哪里了，全wa了，可以过样例

#include<bits/stdc++.h>
#include<iostream>
#define max(A,B) (A<B?B:A)
#define min(A,B) (A>B?B:A)
using namespace std;
const int N=1e6+1000;

char ch[N*40],bj;
int n,x,jis,tot;
int siz[N],lf[N*40],re[N*40],rt[N];

void build(int &bh,int l,int r,int x,char wuy)
{
	int jil=bh;
	bh=++tot;
	lf[bh]=lf[jil],re[bh]=re[jil];
	if(l==r){
		ch[bh]=wuy;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) build(lf[bh],l,mid,x,wuy);
	else build(re[bh],mid+1,r,x,wuy); 
} 

char cx(int bh,int l,int r,int x)
{
	if(l==r) return ch[bh];	
	int mid=(l+r)>>1;
	if(x<=mid) return cx(lf[bh],l,mid,x);
	return cx(re[bh],mid+1,r,x);
}

signed main(){
	cin>>n;char c;
	for(int i=1;i<=n;i++)
	{
		cin>>bj;
		if(bj=='T'){
			cin>>c;jis++;siz[jis]=siz[jis-1]+1; 
			rt[jis]=rt[jis-1];
			build(rt[jis],1,N,siz[jis],c);
		}
		if(bj=='U'){
			cin>>x;siz[++jis]=siz[jis-x-1];
			rt[jis]=rt[jis-x-1];
		}
		if(bj=='Q'){
			cin>>x;
			cout<<cx(rt[jis],1,N,x)<<'\n';
		}
	}
}