主席树？不会。

只会暴力数据结构和 ST 表。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fa[N],lst[N],dep[N],st[N][21],tsp,cnt;char a[N];
signed main()
{
	int q,pos=0;cin>>q;
	for(int i=1;i<=q;i++)
	{
		string s;cin>>s;
		if(s[0]=='T')
		{
			string s1;cin>>s1;
			tsp++;
			fa[tsp]=pos;dep[tsp]=dep[pos]+1;
			st[tsp][0]=pos;for(int i=1;i<=20;i++)st[tsp][i]=st[st[tsp][i-1]][i-1];
			pos=lst[++cnt]=tsp;
			a[tsp]=s1[0];
		}
		else if(s[0]=='U')
		{
			int x;cin>>x;
			cnt-=x;int pos1=lst[cnt];
			pos=lst[++cnt]=pos1;
		}
		else 
		{
			int x;cin>>x;int res=pos,x1=dep[pos]-x;
			for(int i=20;i>=0;i--)if((1<<i)<=x1)x1-=(1<<i),res=st[res][i];
			cout<<a[res]<<'\n';
		}
	}
	return 0;
}

C51 可持久化线段树 P1383 高级打字机

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define mid ((l + r) >> 1)
struct node{int ls,rs,siz;char c;}tr[N*20];int trlen,rt[N],rtnum;
void pushup(int p){ tr[p].siz = tr[lc(p)].siz + tr[rc(p)].siz; }
void change(int pre,int &now, int l, int r, char c)// 点修
{              
    now = ++trlen; tr[now]=tr[pre];
    if (l == r)
    {
        tr[now].siz= 1;
        tr[now].c= c;
        return;
    }
    if (tr[lc(now)].siz < mid - l + 1)
        change(lc(pre), lc(now), l, mid, c);
    else
        change(rc(pre), rc(now), mid + 1, r, c);
    pushup(now);
}
char query(int now, int l, int r, int x)// 点查
{ 
    if (l == r)return tr[now].c;
    if (x <= tr[lc(now)].siz) return query(lc(now), l, mid, x);
    else                    return query(rc(now), mid + 1, r, x - tr[lc(now)].siz);
}
int main()
{
    int n;cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char op;cin >> op;
        if (op == 'T')// 在文章末尾添加一个字母
        { 
            char c;cin >> c;
            ++rtnum;
            change(rt[rtnum - 1], rt[rtnum], 1, n, c);
        }
        if (op == 'U')// 撤销最后的x次修改操作
        { 
            int x;cin >> x;
            ++rtnum;
            rt[rtnum] = rt[rtnum - x - 1];
        }
        if (op == 'Q')// 查询第x个字母
        { 
            int x;cin >> x;
            cout << query(rt[rtnum], 1, n, x) << endl;
        }
    }
    return 0;
}