高级打印机

【题目描述】
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功
能，厉害吧。
请为这种高级打字机设计一个程序，支持如下 3 种操作：
1.T x：在文章末尾打下一个小写字母 x。(type 操作)
2.U x：撤销最后的 x 次修改操作。（Undo 操作）
（注意 Query 操作并不算修改操作）
3.Q x：询问当前文章中第 x 个字母并输出。（Query 操作）
文章一开始可以视为空串。
【输入格式】
第 1 行：一个整数 n，表示操作数量。
以下 n 行，每行一个命令。保证输入的命令合法。
【输出格式】
每行输出一个字母，表示 Query 操作的答案。
【样例输入】
7
T a
T b
T c
Q 2
U 2
T c
Q 2
【样例输出】
b
c
【数据范围】
对于 20%的数据 n<=200；
对于 50%的数据 n<=100000；保证 Undo 操作不会撤销 Undo 操作；

离线算法

#include<bits/stdc++.h>
using namespace std;
struct oppo {
    int to,next;
} rood[100005];
vector < int > q[100005];
int tot_q,ans[100005],a,n,tot,head[100005],all;
char T,t,sc[100005],v[100005],k[100005];
void add(int u,int v) {
    rood[++all].to=v;
    rood[all].next=head[u];
    head[u]=all;
}
void dfs(int x,int tot) {
    if(v[x]||x==0)    k[tot]=v[x];
    else    tot--;
    if(q[x].size())
        for(int i=0; i<q[x].size(); i++)
            sc[q[x][i]]=k[ans[q[x][i]]];
    for(int i=head[x]; i; i=rood[i].next)
        dfs(rood[i].to,tot+1);//向下搜索
}
int main() {
    freopen("a.in","r",stdin);
    freopen("c.out","w",stdout);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>T;
        if(T=='T') {
            cin>>t;
            v[++tot]=t;
            add(tot-1,tot);
        } else if(T=='U') {
            cin>>a;
            ++tot;
            add(tot-a-1,tot);
        } else if(T=='Q') {
            cin>>a;
            q[tot].push_back(++tot_q);
            ans[tot_q]=a;
        }
    }
    dfs(0,0);
    for(int i=1; i<=tot_q; i++)
        cout<<sc[i]<<endl;
    return 0;
}