主席树
一发主席树解决。
插入操作十分显然。
撤销操作复制前面的版本就行。
询问操作十分显然。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000005
int n,lc[N],rc[N],rt[N],len[N],tot,k;
char a[N],p[],z[];
#define mid (l+r)/2
void update(int &o,int pre,int x,int l,int r){
o=++tot;
if(l>=r){scanf("%s",z);a[o]=z[];return ;}
lc[o]=lc[pre]; rc[o]=rc[pre];
if(x<=mid) update(lc[o],lc[pre],x,l,mid);
else update(rc[o],rc[pre],x,mid+,r);
}
void ask(int o,int x,int l,int r){
if(l>=r) {printf("%c\n",a[o]);return ;}
if(x<=mid) ask(lc[o],x,l,mid);
else ask(rc[o],x,mid+,r);
}
int main(){
scanf("%d",&n);
for(int i=,q;i<=n;++i){
scanf("%s",p);
if(p[]=='T'){
++k;len[k]=len[k-]+;
update(rt[k],rt[k-],len[k],,n);
}else if(p[]=='Q') scanf("%d",&q),ask(rt[k],q,,n);
else if(p[]=='U'){
scanf("%d",&q);++k;
len[k]=len[k-q-];rt[k]=rt[k-q-];//复制版本
}
}return ;
}