记录编号	583160	评测结果	AAAAAAAAAA
题目名称	高级打字机	最终得分	100
用户昵称	zxhhh	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2023-10-05 15:02:41	内存使用	32.97 MiB

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5+5; 
int n, top;
struct node {
    int ls, rs, v; char c;
}nds[N<<5]; 
struct seg {
    int rt; 
    inline void push_up (int p) { nds[p].v = nds[nds[p].ls].v+nds[nds[p].rs].v; }
    int add (int p, int l, int r, char k) {
        nds[++top] = nds[p]; p = top; 
        if (l == r) return ++nds[p].v, nds[p].c = k, p;
        int mid = l+r>>1; 
        if (nds[nds[p].ls].v < mid-l+1) nds[p].ls = add(nds[p].ls, l, mid, k); 
        else nds[p].rs = add(nds[p].rs, mid+1, r, k); 
        push_up(p); 
        return p;
    }
    char query (int p, int l, int r, int idx) {
        if (l == r) return nds[p].c; 
        int mid = l+r>>1; 
        if (nds[nds[p].ls].v >= idx) return query(nds[p].ls, l, mid, idx);
        return query(nds[p].rs, mid+1, r, idx-nds[nds[p].ls].v); 
    }
}tr[N];

int main () {
    freopen("type.in", "r", stdin); 
    freopen("type.out", "w", stdout); 
    scanf("%d", &n);
    int t = 0, p = 0, lth = n;  
    while (n--) {
        char op, c; int x; 
        scanf(" %c", &op); 
        if (op == 'Q') scanf("%d", &x), printf("%c\n", tr[t].query(tr[t].rt, 1, lth, x)); 
        else {
            ++t; 
            if (op == 'T') {
                scanf(" %c", &c); tr[t].rt = tr[t].add(tr[t-1].rt, 1, lth, c);
            }
            else {
                scanf("%d", &x); 
                tr[t].rt = tr[t-x-1].rt; 
            }
        }
    }
    return 0;
}