性感代码在线求条

//P1383 高级打字机
#include<bits/stdc++.h>
using namespace std;
#define emdl '\n'
const int MAXN=1e5+5;

struct node{
	int l,r;
	char ch;
	int size;
}tr[40*MAXN];

int n;
int root[MAXN];
int idx;
int len[MAXN];

int build(int l,int r){
	int p=++idx;
	tr[p].size=0;
	if(l==r){
		return p;
	}
	
	int mid=l+r>>1;
	tr[p].l=build(l,mid);
	tr[p].r=build(mid+1,r);
	
	return p;
}

int insert(int pre,int l,int r,int pos,char c){
	int cur=++idx;
	tr[cur]=tr[pre];
	
	if(l==r){
		tr[cur].ch=c;
		tr[cur].size=1;
		return cur;
	}
	
	int mid=l+r>>1;
	if(pos<=mid+tr[tr[pre].l].size){
		tr[cur].l=insert(tr[pre].l,l,mid,pos,c);
	}
	else{
		tr[cur].r=insert(tr[pre].r,mid+1,r,pos-tr[tr[pre].l].size,c);
	}
	
	tr[cur].size=tr[tr[cur].l].size+tr[tr[cur].r].size;
    return cur;
}

char query(int p,int l,int r,int pos){
	if(l==r){
		return tr[p].ch;
	}
	
	int mid=l+r>>1;
	int left_size=tr[tr[p].l].size;
	
	if(pos<=left_size){
		return query(tr[p].l,l,mid,pos);
	}
	else{
		return query(tr[p].r,mid+1,r,pos-left_size);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	cin>>n;
	
	idx=0;
	root[0]=build(1,n);
	len[0]=0;
	
	for(int i=1;i<=n;i++){
		char op;
		cin>>op;
		
		if(op=='T'){
			char x;
			cin>>x;
			
            root[i]=insert(root[i-1],1,n,len[i-1]+1,x);
            len[i]=len[i-1]+1;
		}
		else if(op=='U'){
			int x;
			cin>>x;
			
			root[i]=root[i-x-1];
            len[i]=len[i-x-1];
		}
		else if(op=='Q'){
            int x;
            cin>>x;
            
            char ans=query(root[i-1],1,n,x);
            cout<<ans<<emdl;
            
            root[i]=root[i-1];
            len[i]=len[i-1];
        }
	}

	return 0;
}