https://www.luogu.com.cn/problem/P1383

把数组当作一条链，主席树每一个根节点代表一个数，每一个root代表当前操作（添加）到这个数的当时状态

const int N = 1000010;
#define mid  ((l+r)>>1)
int root[N], tot, cnt;
int ls[N * 20], rs[N * 20], sum[N * 20];
char ch[N * 20];
void push_up(int u)
{
    sum[u] = sum[ls[u]] + sum[rs[u]];
}
void change(int& u, int v, int l, int r, char c)
{
    u = ++tot;
    ls[u] = ls[v];
    rs[u] = rs[v];
    sum[u] = sum[v];
    if (l == r)
    {
        sum[u] = 1;
        ch[u] = c;
        return;
    }
    if (sum[ls[u]] < mid - l + 1) change(ls[u], ls[v], l, mid, c);
    else change(rs[u], rs[v], mid + 1, r, c);
   push_up(u);
}
char find(int u, int l, int r, int x)
{
    if (l == r)  return ch[u];
    if (x <= sum[ls[u]]) return find(ls[u], l, mid, x);
    else return find(rs[u], mid + 1, r, x-sum[ls[u]]);
}
void solve()
{
    int n;
    cin >> n;
    int nn = n;
    while (nn--)
    {
        char o;
        cin >> o;
        if (o == 'T')
        {
            ++cnt;
            char a;
            cin >> a;
            change(root[cnt], root[cnt - 1], 1, n, a);
        }
        else if (o == 'U')
        {
            ++cnt;
            int x;
            cin >> x;
            root[cnt] = root[cnt - x - 1];
        }
        else
        {
            int x;
            cin >> x;
            cout << find(root[cnt], 1, n, x) << '\n';
        }
    }
}