rt,P1383的代码,去掉t[p].ls=++tot;t[p].rs=++tot; 会WA一半的点 加上就过了

#include<bits/stdc++.h>
using namespace std;
const long long N=15000000;
long long tot=0,n,root[N],m,sum=0,len[N];
struct xds{
	struct treee{
		long long data,ls,rs;
	}t[N<<2];
	long long find(long long &p,long long l,long long r,long long K){
		if(l==r){
			return t[p].data;
		}
		long long mid=(l+r)/2;
		if(mid>=K)return find(t[p].ls,l,mid,K);
		if(mid<K)return find(t[p].rs,mid+1,r,K);
	}
	void newpo(long long &p,long long &i,long long l,long long r,long long num,long long x){
		if(!p)p=++tot;
		t[p]=t[i];
		if(l==r){
			t[p].data=x;
			return ;
		}
		long long mid=(l+r)/2;
		if(mid>=num){
			//t[p].ls=++tot;这里
			newpo(t[p].ls,t[i].ls,l,mid,num,x);
		}
		if(mid<num){
			//t[p].rs=++tot;这里
			newpo(t[p].rs,t[i].rs,mid+1,r,num,x);
		}
	}
}f;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(long long i=1;i<=n;i++){
		char ck;
		cin>>ck;
		if(ck=='T'){
			char te;
			cin>>te;
			++sum;
			len[sum]=len[sum-1]+1;
			f.newpo(root[sum],root[sum-1],1,n,len[sum],(long long)te);
		}else if(ck=='U'){
			long long x;
			cin>>x;
			++sum;
			long long hs=max(0,sum-x-1);
			root[sum]=root[hs];
			len[sum]=len[hs];
		}else if(ck=='Q'){
			long long x;
			cin>>x;
			long long an=f.find(root[sum],1,n,x);
			cout<<((char)an)<<"\n";
		}
	}
	return 0;
}